# Difference between revisions of "Ford Fulkerson Algorithm"

Yashsherry (talk | contribs) |
Yashsherry (talk | contribs) |
||

(3 intermediate revisions by the same user not shown) | |||

Line 2: | Line 2: | ||

Year : 1956 | Year : 1956 | ||

Family : [[ | Family : [[Maximum Flow]] | ||

Authors : Edsger W. Dijkstra | Authors : Edsger W. Dijkstra | ||

Line 12: | Line 12: | ||

== Problem Statement == | == Problem Statement == | ||

The | In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem. | ||

== PseudoCode == | == PseudoCode == | ||

Line 31: | Line 31: | ||

■ Disjoint paths and network connectivity. | ■ Disjoint paths and network connectivity. | ||

■ Bipartite matchings. | ■ Bipartite matchings. | ||

■ Circulations with upper and lower bounds. | ■ Circulations with upper and lower bounds. | ||

■ Census tabulation (matrix rounding). | ■ Census tabulation (matrix rounding). | ||

■ Airline scheduling. | ■ Airline scheduling. | ||

■ Image segmentation. | ■ Image segmentation. | ||

■ Project selection (max weight closure). | ■ Project selection (max weight closure). | ||

■ Baseball elimination. | ■ Baseball elimination. | ||

== Implementations == | == Implementations == | ||

JS : https://github.com/prabod/Graph-Theory-Ford-Fulkerson-Maximum-Flow | |||

Python : https://github.com/odubno/ford-fulkerson-max-flow |

## Latest revision as of 12:48, 22 September 2021

## Algorithm Details

Year : 1956

Family : Maximum Flow

Authors : Edsger W. Dijkstra

Paper Link : http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf

Time Complexity :

## Problem Statement

In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem.

## PseudoCode

1 flow = 0 2 for each edge (u, v) in G: 3 flow(u, v) = 0 4 while there is a path, p, from s -> t in residual network G_f: 5 residual_capacity(p) = min(residual_capacity(u, v) : for (u, v) in p) 6 flow = flow + residual_capacity(p) 7 for each edge (u, v) in p: 8 if (u, v) is a forward edge: 9 flow(u, v) = flow(u, v) + residual_capacity(p) 10 else: 11 flow(u, v) = flow(u, v) - residual_capacity(p) 12 return flow

## Applications

■ Disjoint paths and network connectivity.

■ Bipartite matchings.

■ Circulations with upper and lower bounds.

■ Census tabulation (matrix rounding).

■ Airline scheduling.

■ Image segmentation.

■ Project selection (max weight closure).

■ Baseball elimination.

## Implementations

JS : https://github.com/prabod/Graph-Theory-Ford-Fulkerson-Maximum-Flow