Ford Fulkerson Algorithm

Algorithm Details

Year : 1956

Family : Shortest Path(Directed graphs)

Authors : Edsger W. Dijkstra

Time Complexity :

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.

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.