One of the last classes I took at Washington State University was Network Optimization taught by Bala Krishnamoorthy. The class focused on solving problems related to networks, and building our definitions and tools for understanding them on a large scale. In this context a network is a general concept, nodes connected by arcs representing any number of natural and man made structures. For our final we were asked to implement three different algorithms that solved a “Max Flow” problem. A Max Flow problem is a fairly simple idea, given a network, how do you send as much flow as possible from node S (source) to node T (terminus). A practical application would be, Given the interstate highway system of Pennsylvania, what is the maximum number of cars that could travel from Philadelphia to Pittsburgh in one day?
While all three of my implementations worked, their run times were not great. I also believe that I implemented one of the three algorithms, the Preflow Push Algorithm, in the most hamfisted way possible. My report can be found here. I intend to post the matlab code for my three algorithms, as well as the algorithm for generating test networks once I am more comfortable with github. I have already begun revisions on this project. I want to make the Preflow Push Algorithm work correctly.