Max Flow Algorithms : Ford-Fulkerson, Edmond-Karp, Goldberg-TarjanComparison in regards to practical running time on different types of randomized  flow networks.

Abstract: The original algorithm proposed by Ford and Fulkerson to solve the maximum flow problem is still in use but is far from the only alternative. This paper introduces that algorithm as well as the similar Edmond-Karp and the more modern Goldberg-Tarjan. Ford-Fulkerson uses depth-first-searches to find augmenting paths through a residual graph. Edmond-Karp instead uses breath-first-searches to achieve a polynomial time complexity. Goldberg-Tarjan solves the problem by gradually pushing flow through the residual graph.  A comparison on randomized graphs where the size, graph density and the maximum edge capacity was varied one at a time was performed. The results show that the Goldberg-Tarjan algorithm has higher performance than the others, but only if it uses heuristics.