*In which we discuss the worst-case running of the Ford-Fulkerson algorithm, discuss plausible heuristics to choose an augmenting path in a good way, and begin analyzing the “fattest path” heuristic.*

In the last lecture we proved the Max-Flow Min-Cut theorem in a way that also established the optimality of the Ford-Fulkerson algorithm: if we iteratively find an augmenting path in the residual network and push more flow along that path, as allowed by the capacity constraints, we will eventually find a flow for which no augmenting path exists, and we proved that such a flow must be optimal.

Each iteration of the algorithm takes linear time in the size of the network: the augmenting path can be found via a DFS of the residual network, for example. The problem is that, in certain cases, the algorithm might take a very long time to finish. Consider, for example, the following network.

Suppose that, at the first step, we pick the augmenting path . We can only push one unit of flow along that path. After this first step, our residual network (not showing edges out of and into , which are never used in an augmenting path) is

Now it is possible that the algorithm picks the augmenting path along which, again, only one unit of flow can be routed. We see that, indeed, it is possible for the algorithm to keep picking augmenting paths that involve a link between and , so that only one extra unit of flow is routed at each step.

The problem of very slow convergence times as in the above example can be avoided if, at each iteration, we choose more carefully which augmenting path to use. One reasonable heuristic is that it makes sense to pick the augmenting path along which the most flow can be routed in one step. If we had used such an heuristic in the above example, we would have found the optimum in two steps. Another, alternative, heuristic is to pick the shortest augmenting path, that is, the augmenting path that uses the fewest edges; this is reasonable because in this way we are going to use the capacity of fewer edges and keep more residual capacity for later iterations. The use of this heuristic would have also resulted in a two-iterations running time in the above example.

**1. The “fattest” augmenting path heuristic **

We begin by studying the first heuristic: that is we consider an implementation of the Ford-Fulkerson algorithm in which, at every iteration, we pick a *fattest* augmenting path in the residual network, where the fatness of a path in a capacitated network is the minimum capacity of the edges in the path. In the network of our previous example, the paths and have fatness , while the path has fatness .

How do we find a fattest augmenting path? We will show that it can be found with a simple modification of Dijkstra’s algorithm for finding shortest paths.

** 1.1. Dijkstra’s algorithm **

Let us first quickly recall how Dijkstra’s algorithm works. Suppose that we have a graph in which each edge has a length and, for two given vertices , we want to find the path of minimal length from to , where the length of a path is the sum of the lengths of the edges in the path. The algorithm will solve, for free, the more general problem of computing the length of the shortest path from to for every vertex . In the algorithm, the data structure that holds information about a vertex has two fields: , which will eventually contain the length of the shortest path from to , and which will contain the *predecessor* of in a shortest path from to , that is, the identity of the vertex that comes immediately before in such a path.

The distances are initialized to , except for which is initialized to zero. The algorithm initially puts all vertices in a *priority queue* . Recall that a priority queue is a data structure that contains elements which have a numerical field called a *key* (in this case the key is the *dist* field), and that supports the operation of inserting an element in the queue, of finding and removing from the queue the element of minimal key value, and of reducing the key field of a given element.

The algorithm works as follows:

Algorithm *Dijkstra*

- Input: graph , vertex , non-negative edge lengths
- for each , let
- insert all vertices in a priority queue keyed by the
*dist*field - while is not empty
- find and remove vertex in whose field is smallest among queue elements
- for all vertices such that
- if then
- update to reflect changed value of

- if then

The running time is equal to whatever time it takes to execute *insert* operations, *remove-min* operations, and *reduce-key* operations in the priority queue. The simple implementation of a priority queue via a binary heap gives running time for each operation, and a total running time of . A more elaborate data structure called a *Fibonacci heap* implements *insert* and *remove-min* in time, and is such that *decrease-key* operations always take at most time overall, so that the total running time is .

Regarding correctness, we can prove by induction that the algorithm maintains the following invariant: at the beginning of each iteration of the *while* loop, the vertices which are *not* in the queue are such that is the correct value of the shortest path length from to and such a shortest path can be realized by combining a shortest path from to and then continuing with the edge . This is certainly true at the beginning, because the first vertex to be removed is , which is at distance from itself, and if it is true at the end, when the queue is empty, it means that at the end of the algorithm all vertices get their correct values of and . So we need to show that if the invariant is true at a certain step then it is true at the following step.

Basically, all we need to prove is that, at the beginning of each iteration, the vertex that we remove from the queue has correct values of and . If we call , then is a vertex that was removed from the queue at an earlier iteration and so, by the inductive hypothesis, is such that is the correct shortest path distance from to ; if we also have , which means that there is indeed a path of length from to in which is the predecessor of . We need to prove that this path is a shortest path. So suppose toward a contradiction that there is a shorter path of length . The path starts at , which is outside the queue, and ends at , which is in the queue, so at some point the path must have an edge such that is outside the queue and is inside. This also means that when was removed from the queue it had the correct value , and after we processed the neighbors of we had . But this would mean that is at most the length of the path , while is bigger than the length of the path , which is impossible because was chosen to be the element with the smallest among elements of the queue.

** 1.2. Adaptation to find a fattest path **

What would be the most straightforward adaptation of Dijkstra’s algorithm to the problem of finding a fattest path? In the shortest path problem, the length of a path is the *sum* of the *lengths* of the edges of the path, and we want to find a path of *minimal* length; in the fattest path problem, the fatness of a path is the *minimum* of the *capacities* of the edges of the path, and we want to find a path of *maximal* fatness. So we just change sums to , lengths to capacities, and minimization to maximization.

Algorithm *Dijkstra-F*

- Input: graph , vertex , non-negative edge capacities
- for each , let
- insert all vertices in a priority queue keyed by the
*dist*field - while is not empty
- find and remove vertex in whose field is largest among queue elements
- for all vertices such that
- if then
- update to reflect changed value of

- if then

The running time is the same and, quite amazingly, the proof of correctness is also essentially the same. (Try writing it up.)

Remark 1A useful feature of Dijkstra’s algorithm (and other shortest path algorithms) is that it works to find “best” paths for a lot of different measures of “cost” for a path, besides length and fatness. Basically, the only requirements to implement the algorithm and prove correctness are:

- The cost of a path is no better than the cost of an initial segment , of the path. That is, if we are trying to maximize the cost, we need the property that the cost of a path is at most the cost of any initial segment (e.g., the fatness of a path is at most the fatness of any initial segment, because in the former case we are taking the minimum over a larger set of capacities); if we are trying to minimize the cost, we need the property that the cost of a path is at least the cost of any initial segment.
- The cost of a path can be determined by only knowing the cost of the path and the cost of the edge .

** 1.3. Analysis of the fattest augmenting path heuristic **

In the next lecture, we will prove the following result.

Theorem 1If is a network in which the optimal flow has cost , then there is a path from to of fatness .

From the above theorem, we se that if we implement the Ford-Fulkerson algorithm with the fattest-path heuristic, then, after we have found augmenting paths, we have a solution such that, in the residual network, the optimum flow has cost at most .

To see why, call the cost of the flow found by the algorithm after iterations, and the optimum of the residual network after iterations of the algorithm. Clearly we have .

The theorem tells us that at iteration we are going to find an augmenting path of fatness at least . (Because of the “virtual capacities,” the residual network could have as many as twice the number of edges of the original network, but no more.) This means that the cost of the flow at the end of the -th iteration is going to be , which means that the residual optimum is going to be

We started with and , and so we must have .

If the capacities are integers, then if the residual network has an optimum less than 1, its optimum must be zero. Recalling that ,

This means that if , then , which implies and so it means that, within the first steps, the algorithm reaches a point in which the residual network has no augmenting path and it stops.

We said that, using the simple binary heap implementation of Dijkstra’s algorithm, the running time of one iteration is , and so we have the following analysis.

Theorem 2The fattest-path implementation of the Ford-Fulkerson algorithm, given in input a network with integer capacities whose optimal flow has cost , runs in time at most

To complete the above running time analysis, we need to prove Theorem 1, which we will do next time.