ON MAXIMUM FLOW OF NETWORKS

Abstract

This paper aims to introduce and discuss two existing algorithms, namely Ford-Fulkerson’s Algorithm and Dinic’s Algorithm. These algorithms are for determining the maximum flow from source (s) to sink (t) in a flow network. A numerical example is solved to illustrate both algorithms, and to demonstrate, study, and compare the procedures at each iteration. The results show that Dinic’s Algorithm returns the maximum flow that takes less number of iterations and augmentations than the Ford-Fulkerson Algorithm. In terms of complexity, the running time of Dinic’s algorithm is , which should make it perform better on dense graphs. This goes to show that the claim by many researchers that Dinic’s Algorithm is very powerful in solving big network flow problems is justified.