6.5.2. The Algorithm

The successive shortest paths algorithm once again assumes that all edge capacities are integers, but it does not require the edge costs to be integers.

It does assume, however, that all edges have non-negative costs and that there exists an uncapacitated path between every pair of vertices in \(G\).

Non-negative edge costs can be guaranteed using the transformation from Section 6.3.4, if necessary after applying the transformation from Section 6.3.2 to ensure that all edge capacities are finite. Then we can apply the transformation from Section 6.3.1 to ensure the existence of an uncapacitated path between all pairs of vertices. Note, however, that if \(C\) once again refers to an upper bound on the absolute values of the edge costs, and \(U\) refers to an upper bound on the absolute values of the vertex supply balances and edge capacities, then these transformations may increase both \(C\) and \(U\) by a factor polynomial in \(n\) and \(m\).¹ The successive shortest paths algorithm maintains a pseudo-flow \(f\) and a potential function \(\pi\) that satisfy the following invariant, where \(c^\pi_e\) once again refers to the reduced cost of an edge \(e \in G^f\) with respect to the current potential function \(\pi\).

Invariant 6.20: \(c^\pi_{x,y} \ge 0\) for every edge \((x, y) \in G^f\).

By Lemma 6.2, this implies that once \(f\) is a flow, it is a minimum-cost flow. Initially, we set \(f_{x,y} = 0\) for every edge \((x, y) \in G\) and \(\pi_x = 0\) for every vertex \(x \in G\). This ensures that \(G^f = G\) at the beginning of the algorithm and, since \(c_{x,y} \ge 0\) for every edge \((x, y) \in G\), that \(c^\pi_{x,y} = c_{x,y} - \pi_x + \pi_y \ge 0\) for every edge \((x, y) \in G^f\). Thus, Invariant 6.20 holds initially.

The remainder of the algorithm proceeds in iterations. If there is no vertex in \(G^f\) with non-zero excess, then \(f\) is a flow. Thus, since \(f\) satisfies Invariant 6.20, it is a minimum-cost flow, by Lemma 6.2, and the algorithm terminates.

If there exists a vertex with non-zero excess, then observe that the existence of a vertex with positive excess implies the existence of a vertex with negative excess and vice versa (because the total excess of all vertices is zero).

Since there exists an uncapacitated path between every pair of vertices in \(G\) and every uncapacitated edge in \(G\) is easily seen to be in \(G^f\), there exists a path in \(G^f\) from every vertex with positive excess to every vertex with negative excess.

The algorithm picks an arbitrary vertex \(s\) with positive excess and finds a shortest path \(P\) in \(G^f\) to an arbitrary vertex \(t\) with negative excess, using the reduced edge costs \(c^\pi\) as the edge lengths for the shortest paths computation. Hence the algorithm's name. The proof of Lemma 6.21 below demonstrates why it is important that \(P\) is a shortest path. Since the reduced edge costs are non-negative, shortest paths from \(s\) to all vertices in \(G^f\) with respect to the reduced edge costs as edge lengths can be found in \(O(n \lg n + m)\) time using Dijkstra's algorithm.

Let

\[\delta = \min \left(e_s, -e_t, \left\{ u^f_{x,y} \mid (x, y) \in P \right\}\right)\]

and, for each vertex \(x \in V\), let \(d_x\) be the distance from \(s\) to \(x\) in \(G^f\) with respect to the reduced edge costs. Then we replace \(f\) with the pseudo-flow \(f'\) and \(\pi\) with the potential function \(\pi'\) defined as

\[f'_{x,y} = \begin{cases} f_{x,y} + \delta & \text{if } (x, y) \in P\\ f_{x,y} - \delta & \text{if } (y, x) \in P\\ f_{x,y} & \text{otherwise} \end{cases}\]

and

\[\pi'_x = \pi_x - d_x \quad \forall x \in V.\]

By Lemma 5.1, \(f'\) is indeed a pseudo-flow (because we update the flow amounts along the edges along a path in \(G^f\) in the same way the Augment procedure does). By the next lemma, replacing \(f\) and \(\pi\) with \(f'\) and \(\pi'\) maintains Invariant 6.20.

Lemma 6.21: If \(c^\pi_{x,y} \ge 0\) for every edge \((x, y) \in G^f\), then \(c^{\pi'}_{x,y} \ge 0\) for every edge \((x, y) \in G^{f'}\).

Proof: Consider any edge \((x, y) \in G^{f'}\). We distinguish two cases:

If \((x, y)\) is an edge of \(G^f\), then \(d_y \le d_x + c^\pi_{x,y}\), which implies that

\[0 \le c^\pi_{x,y} + d_x - d_y = c_{x,y} - \bigl(\pi_x - d_x\bigr) + \bigl(\pi_y - d_y\bigr) = c_{x,y} - \pi'_x + \pi'_y = c^{\pi'}_{x,y}.\]

If \((x, y)\) is not an edge of \(G^f\), then \((y, x)\) must be an edge of \(P\) because only the reversals of edges in \(P\) can be added to \(G^{f'}\). Thus,

\[d_x = d_y + c^\pi_{y,x}\]

(because \(P\) is a shortest path), that is,

\[0 = c^\pi_{y,x} + d_y - d_x = c^{\pi'}_{y,x}.\]

Since \(c^{\pi'}_{x,y} = -c^{\pi'}_{y,x}\), this shows that, once again, \(c^{\pi'}_{x,y} \ge 0\). ▨

By Lemma 6.2 and Invariant 6.20, once the successive shortest paths algorithm terminates, the current pseudo-flow \(f\) is a minimum-cost flow. It remains to bound how long it takes for the algorithm to terminate.

Theorem 6.22: The successive shortest paths algorithm takes \(O\bigl(U\bigl(n^2 \lg n + nm\bigr)\bigr)\) time to compute a minimum-cost flow in a network whose vertices have integer supply balances between \(-U\) and \(U\) and whose edges have integral capacities.

Proof: The initialization of the successive shortest paths algorithm clearly takes \(O(n + m)\) time.

Each iteration requires solving the single-source shortest paths problem in a residual network with non-negative edge lengths and updating the pseudo-flow, node potentials, residual network, and (implicitly) the reduced edge costs. This takes \(O(n \lg n + m)\) time if we use Dijkstra's algorithm to compute shortest paths. Thus, it suffices to prove that the algorithm terminates after at most \(\frac{Un}{2}\) iterations.

Since each iteration of the algorithm sends an integral positive amount of flow \(\delta\) from a node \(s\) with positive excess to a node \(t\) with negative excess, it reduces the excess of \(s\) by \(1 \le \delta \le e_s\), increases the excess of \(t\) by \(1 \le \delta \le -e_t\), and does not change the excess of any other vertex. Thus, the absolute excess \(\sum_{x \in V} |e_x|\) decreases by at least two in each iteration. The initial absolute excess is at most \(Un\) because \(|b_x| \le U\) for all \(x \in V\). Thus, it takes at most \(\frac{Un}{2}\) iterations before every node has excess \(0\). ▨