KEMBAR78
Ford Fulkerson Algorithm | PDF | Combinatorial Optimization | Combinatorics
Scribd
Upload
278 views16 pages

Ford Fulkerson Algorithm

This document demonstrates the Ford-Fulkerson algorithm for finding the maximum flow in a network. It shows the original network and residual network. It then iteratively finds augmenting paths from the source node s to the sink node t, sends flow along each path equal to the path's minimum capacity, and updates the residual capacities, until there are no more augmenting paths. The final network shows the maximum flow has been found.

Uploaded by

manishbhardwaj8131
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
278 views16 pages

Ford Fulkerson Algorithm

This document demonstrates the Ford-Fulkerson algorithm for finding the maximum flow in a network. It shows the original network and residual network. It then iteratively finds augmenting paths from the source node s to the sink node t, sends flow along each path equal to the path's minimum capacity, and updates the residual capacities, until there are no more augmenting paths. The final network shows the maximum flow has been found.

Uploaded by

manishbhardwaj8131
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 16

15.082 & 6.855J & ESD.

78J Algorithm Visualization

The Ford-Fulkerson Augmenting Path Algorithm for the Maximum Flow Problem

Ford-Fulkerson Max Flow


4

2
3
2

5
1
1 2

s
3

4
1
2

3
4 3 2 s 3 4 1 3 2 1 1 2 2 5 1 t

This is the original network, and the original residual network.


3

Ford-Fulkerson Max Flow


4

2
3
2

5
1
1 2

s
3

4
1
2

3
4 3 2 s 3 4 1 3 2 1 1 2 2 5 1 t

Find any s-t path in G(x)

Ford-Fulkerson Max Flow


4

2
3
2

5
1
1 1 2

s
2 3 1

4
1

2 1

3
4 3 2 s 3 4 1 3 2 1 1 2 2 5 1 t

Determine the capacity of the path. Send units of flow in the path. Update residual capacities.
5

Ford-Fulkerson Max Flow


4

2
3
2

5
1
1 1 2

s
2 3 1

4
1

2 1

3
4 3 2 s 3 4 1 3 2 1 1 2 2 5 1 t

Find any s-t path

Ford-Fulkerson Max Flow


4

2
3
2 1

5
1
1 1 1 1

s
2 3 1

4
1

2 1 1 1

3
4 3 2 s 3 4 1 3 2 1 1 2 2 5 1 t

Determine the capacity of the path. Send units of flow in the path. Update residual capacities.
7

Ford-Fulkerson Max Flow


4

2
3
2 1

5
1
1 1 1 1

s
2 3 1

4
1

2 1 1 1

3
4 3 2 s 3 4 1 3 2 1 1 2 2 5 1 t

Find any s-t path

Ford-Fulkerson Max Flow


4

2
3
1

5
1
1 1 1 1 2

s
2 3 1

4
1

1 1 2 1

3
4 3 2 s 3 4 1 3 2 1 1 2 2 5 1 t

Determine the capacity of the path. Send units of flow in the path. Update residual capacities.
9

Ford-Fulkerson Max Flow


4

2
3
1 2

5
1
1 1 1 1 2

s
2 3 1

4
1

1 1 2 1

3
4 3 2 s 3 4 1 3 2 1 1 2 2 5 1 t

Find any s-t path

10

Ford-Fulkerson Max Flow


4

2
3
1 2

5
1
1 1 1 1 2

s
1 2 2 1

4
1
1 2 1

1 2

3
4 3 2 s 3 4 1 3 2 1 1 2 2 5 1 t

Determine the capacity of the path. Send units of flow in the path. Update residual capacities.
11

Ford-Fulkerson Max Flow


4

2
3
1 2

5
1
1 1 1 1 2

s
1 2 2 1

4
1
2 1

1 2

3
4 3 2 s 3 4 1 3 2 1 1 2 2 5 1 t

Find any s-t path

12

Ford-Fulkerson Max Flow


4 3

2
3 2
1

5
1 1

s
1 2 2 1

1 2

4
1
2 1

1 2

3
4 3 2 s 3 4 1 3 2 1 1 2 2 5 1 t

Determine the capacity of the path. Send units of flow in the path. Update residual capacities.
13

Ford-Fulkerson Max Flow


4 3

2
3 2
1

5
1 1

s
1 2 2 1

1 2

4
1
2 1

1 2

3
4 3 2 s 3 4 1 3 2 1 1 2 2 5 1 t

There is no s-t path in the residual network. This flow is optimal


14

Ford-Fulkerson Max Flow


4 3

2
3 2
1

5
1 1

s
1 2 2 1

1 2

4
1
2 1

1 2

3
4 3 2 s 3 4 1 3 2 1 1 2 2 5 1 t

These are the nodes that are reachable from node s.

15

Ford-Fulkerson Max Flow


1

2
1
2

5
1
2

s
2

4
2

3
4 3 2 s 3 4 1 3 2 1 1 2 2 5 1 t

Here is the optimal flow

16

MITOpenCourseWare http://ocw.mit.edu

15.082J / 6.855J / ESD.78J Network Optimization


Fall 2010

For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.

You might also like