Difference between revisions of "Ford Fulkerson Algorithm"

From Algorithm Wiki
Jump to navigation Jump to search
 
(3 intermediate revisions by the same user not shown)
Line 2: Line 2:
Year : 1956
Year : 1956


Family : [[Shortest Path(Directed graphs)]]
Family : [[Maximum Flow]]


Authors : Edsger W. Dijkstra
Authors : Edsger W. Dijkstra
Line 12: Line 12:
== Problem Statement ==
== Problem Statement ==


The Single-Source Shortest Path (SSSP) problem consists of finding the shortest paths between a given vertex v and all other vertices in the graph.
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 ==


Python : https://github.com/mburst/dijkstras-algorithm
JS : https://github.com/prabod/Graph-Theory-Ford-Fulkerson-Maximum-Flow


C++ : https://gist.github.com/MagallanesFito/61afb009986f0319774cb079b8914bb2
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

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