Algorithms in a Nutshell

Reflections on Augmenting Paths

Solving the Maximum Flow problem does not help us to immediately solve any of the remaining problems discussed earlier in this chapter. However, by solving the Maximum Flow problem we are inspired to consider a class of similar problems that seek to maximize the flow through a flow network while at the same time minimizing the cost of that flow. If we associate with each edge (u, v) in the network a cost d(u, v) that reflects the per-unit cost of shipping a unit over edge (u, v), then the goal is to minimize:

Σ f(u, v)*d(u, v)

for all edges in the flow network. Now, for Ford-Fulkerson, we stressed the importance of finding an augmenting path that could increase the maximum flow through the network. What if we modify the search routine to find the least costly augmentation, if one exists? We have already seen greedy algorithms (such as Prim's Algorithm for building a Minimum Spanning Tree in Chapter 6) that iteratively select the least costly extension; perhaps such an approach will work here.

To find the least costly augmentation path, we cannot rely strictly on a breadth-first or a depth-first approach. As we saw with Prim's Algorithm, we must use a priority queue to store and compute the distance of each vertex in the flow network from the source vertex. We essentially compute the costs of shipping an additional unit from the source vertex to each vertex in the network, and we maintain a priority queue based on the ongoing computation. As the search ...