A delivery van leaves a depot \(s\) for a customer \(t\) through a road network with four intermediate junctions. Each road segment has a travel time. There are several routes; the driver wants the fastest one, and the dispatcher wants something more: a reason to believe that no faster route exists, short enough to check on the back of an envelope. An electric van complicates matters, because on a long descent it recovers energy, so if the quantity being minimized is energy and not time, some segments have negative cost. The algorithm that works for travel times then gives wrong answers.
This chapter develops shortest paths as the first and cleanest example of a pattern that recurs through the book: an optimization problem over a huge set of combinatorial objects, an algorithm that never looks at most of them, and a certificate, here a set of node labels, that proves the answer optimal. Elementary facts about graphs, paths, and cycles are taken from Discrete Mathematics; what is new is the optimization.
2.1 Distances and the triangle inequality
Definition 2.1 (network, walk, path, distance). A network is a directed graph \(G=(V,A)\) with a length \(c_{vw}\in\mathbb R\) on each arc \((v,w)\) . A walk from \(v_0\) to \(v_k\) is a sequence of nodes \(v_0,v_1,\dots,v_k\) with \((v_{i-1},v_i)\in A\) for each \(i\) ; its length is \(\sum_{i=1}^{k}c_{v_{i-1}v_i}\) , and the walk with \(k=0\) has length zero. A path is a walk with no repeated node, and a cycle is a walk with \(k\ge 1\) and \(v_0=v_k\) whose other nodes are distinct. For a fixed source \(s\) , the distance \(d(v)\) is the minimum length of a path from \(s\) to \(v\) , and \(d(v)=\infty\) if there is none.
A network on \(n\) nodes can have more than \((n-2)!\) paths from \(s\) to \(t\) , so the minimum in the definition is over a set far too large to list. Paths, however, have a property that sets of projects or pallets do not have: a best one is assembled from best pieces.
Lemma 2.2 (walks, paths, and negative cycles). Suppose no cycle reachable from \(s\) has negative length. Then every walk from \(s\) to \(v\) is at least as long as some path from \(s\) to \(v\) , so \(d(v)\) is also the minimum length of a walk from \(s\) to \(v\) . If a cycle of negative length is reachable from \(s\) , then walks from \(s\) to the nodes of that cycle have lengths unbounded below.
Proof. A walk that is not a path repeats a node, so it contains a cycle as a consecutive stretch. Deleting that stretch leaves a walk between the same endpoints with fewer arcs, and its length is smaller by the length of the cycle, which is nonnegative by hypothesis. Repeating the deletion ends, after finitely many steps, with a path no longer than the original walk. For the second statement, a walk may reach the cycle and traverse it any number of times, each traversal lowering the length by a fixed positive amount.
Theorem 2.3 (potentials bound distances). Let \(\pi:V\to\mathbb R\) satisfy \(\pi_s=0\) and
Then \(\pi_v\) is at most the length of every walk from \(s\) to \(v\) ; in particular \(\pi_v\le d(v)\) . If no cycle reachable from \(s\) has negative length and every node is reachable from \(s\) , the distances themselves satisfy these conditions. Consequently a labelling \(\rho\) with \(\rho_s=0\) equals \(d\) if and only if it satisfies the displayed inequalities and each \(\rho_v\) is the length of some walk from \(s\) to \(v\) .
Proof. Let \(s=v_0,v_1,\dots,v_k=v\) be a walk. Adding the inequalities \(\pi_{v_i}-\pi_{v_{i-1}}\le c_{v_{i-1}v_i}\) for \(i=1,\dots,k\) , the left sides telescope to \(\pi_v-\pi_s=\pi_v\) and the right sides add to the length of the walk.
For the distances, \(d(s)=0\) because the empty walk has length zero and, by Lemma 2.2, no walk from \(s\) to \(s\) is shorter. For an arc \((v,w)\) , a shortest path to \(v\) followed by the arc is a walk to \(w\) of length \(d(v)+c_{vw}\) , and Lemma 2.2 gives \(d(w)\le d(v)+c_{vw}\) .
For the last statement, the distances have both properties. Conversely, if \(\rho\) satisfies the inequalities then \(\rho_v\le d(v)\) by the first part, and if \(\rho_v\) is the length of some walk then \(\rho_v\ge d(v)\) by Lemma 2.2.
A function \(\pi\) satisfying the displayed inequalities is called a feasible potential. The inequality \(d(w)\le d(v)+c_{vw}\) is the triangle inequality for distances. Theorem 2.3 is the certificate promised in the opening: to convince someone that a route of length \(12\) is shortest, hand over the route and a potential with \(\pi_t=12\) . Checking the potential takes one comparison per arc, however many routes the network has.
2.2 Dijkstra’s algorithm
When all lengths are nonnegative, distances can be computed by a greedy sweep outward from the source. The algorithm keeps a tentative label \(\rho(v)\) for every node and a set \(S\) of settled nodes whose labels are final.
Start with \(\rho(s)=0\) , \(\rho(v)=\infty\) for \(v\ne s\) , and \(S\) empty. While some unsettled node has a finite label, choose an unsettled node \(v\) with the smallest label and add it to \(S\) ; then relax each arc \((v,w)\) leaving it: if \(\rho(v)+c_{vw}<\rho(w)\) , set \(\rho(w)=\rho(v)+c_{vw}\) and record \(v\) as the predecessor of \(w\) . When the loop ends, the predecessor records form a tree of shortest paths rooted at \(s\) .
Theorem 2.4 (correctness of Dijkstra’s algorithm). If \(c_{vw}\ge 0\) for every arc, then at the moment a node \(v\) is settled its label equals \(d(v)\) , and at termination \(\rho(v)=d(v)\) for every node.
Proof. Every finite label is the length of a walk from \(s\) , namely the one traced back through predecessors, so \(\rho(v)\ge d(v)\) throughout. We show by induction on the order of settling that \(\rho(v)\le d(v)\) when \(v\) is settled. The first node settled is \(s\) , with \(\rho(s)=0=d(s)\) .
Suppose \(v\) is about to be settled and all earlier settled nodes carry their distances. Let \(P\) be any path from \(s\) to \(v\) . It starts in \(S\) and ends outside \(S\) , so it has a first arc \((x,y)\) with \(x\in S\) and \(y\notin S\) . When \(x\) was settled the arc \((x,y)\) was relaxed, so \(\rho(y)\le\rho(x)+c_{xy}=d(x)+c_{xy}\) , and \(d(x)\) is at most the length of the part of \(P\) up to \(x\) . Hence \(\rho(y)\) is at most the length of \(P\) up to \(y\) . The remainder of \(P\) consists of arcs of nonnegative length, so \(\rho(y)\) is at most the length of \(P\) . Finally \(\rho(v)\le\rho(y)\) , because \(v\) was chosen with the smallest label among unsettled nodes. So \(\rho(v)\) is at most the length of every path to \(v\) , that is, \(\rho(v)\le d(v)\) .
A node never settled has label \(\infty\) and is unreachable, since otherwise the argument above applied to a path reaching it would exhibit an unsettled node with a finite label.
Nonnegativity was used exactly once, in the sentence about the remainder of \(P\) . That is the step that fails for the electric van.
Each of the \(n\) rounds scans the labels for a minimum and relaxes the arcs leaving one node, so a direct implementation takes \(O(n^2)\) steps; keeping the labels in a heap reduces this to \(O(m\log n)\) . Either bound involves only \(n\) and \(m\) , not the magnitudes of the lengths, so in the terms of Chapter 1 the algorithm is strongly polynomial.
Example 2.1: Dijkstra’s algorithm on the delivery network
The network has nodes \(s,a,b,c,d,t\) and nine arcs with travel times
The table records the labels after each node is settled; a label is printed in bold in the row in which its node is settled.
| Settled | \(\rho(a)\) | \(\rho(b)\) | \(\rho(c)\) | \(\rho(d)\) | \(\rho(t)\) | Arcs that lowered a label |
|---|---|---|---|---|---|---|
| \(s\) | \(4\) | \(2\) | \(\infty\) | \(\infty\) | \(\infty\) | \((s,a)\) , \((s,b)\) |
| \(b\) | \(3\) | 2 | \(10\) | \(9\) | \(\infty\) | \((b,a)\) , \((b,c)\) , \((b,d)\) |
| \(a\) | 3 | \(2\) | \(8\) | \(9\) | \(\infty\) | \((a,c)\) |
| \(c\) | \(3\) | \(2\) | 8 | \(9\) | \(14\) | \((c,t)\) |
| \(d\) | \(3\) | \(2\) | \(8\) | 9 | \(12\) | \((d,t)\) |
| \(t\) | \(3\) | \(2\) | \(8\) | \(9\) | 12 | none |
Three labels were lowered after first being set. The label of \(a\) dropped from \(4\) to \(3\) when \(b\) was settled, because the detour \(s,b,a\) beats the direct arc. The label of \(c\) dropped from \(10\) to \(8\) , and the label of \(t\) from \(14\) to \(12\) . When \(c\) was settled, its arc to \(d\) offered \(8+2=10\) , which did not beat the existing label \(9\) , so nothing changed.
The distances are \(d(a)=3\) , \(d(b)=2\) , \(d(c)=8\) , \(d(d)=9\) , \(d(t)=12\) . The predecessors are \(b\) for \(a\) , \(s\) for \(b\) , \(a\) for \(c\) , \(b\) for \(d\) , and \(d\) for \(t\) , so the shortest route to the customer is \(s,b,d,t\) with length \(2+7+3=12\) .
Now check the certificate. For each arc compute the slack \(c_{vw}+d(v)-d(w)\) , which Theorem 2.3 requires to be nonnegative:
All nine are nonnegative, so \(d\) is a feasible potential and no walk from \(s\) to \(t\) is shorter than \(12\) . The five arcs with slack zero are exactly the arcs of the shortest-path tree.
The slack of an arc has a direct meaning visible in Figure 2.1. A walk from \(s\) to \(t\) has length equal to \(d(t)\) plus the sum of the slacks of its arcs, by the telescoping computation in the proof of Theorem 2.3. The route \(s,a,c,t\) uses slacks \(1\) , \(0\) , and \(2\) , so its length is \(12+3=15\) , which agrees with \(4+5+6\) .
2.3 Negative lengths and the Bellman–Ford recursion
Example 2.2: One negative arc defeats the greedy choice
Take nodes \(s,a,b,t\) with \(c_{sa}=2\) , \(c_{sb}=5\) , \(c_{ba}=-4\) , and \(c_{at}=1\) . There is no cycle at all, so distances are well defined: \(d(a)=\min\{2,\ 5-4\}=1\) and \(d(t)=2\) .
Dijkstra’s algorithm settles \(s\) , giving labels \(\rho(a)=2\) and \(\rho(b)=5\) . It then settles \(a\) , the smaller label, and relaxes \((a,t)\) to get \(\rho(t)=3\) . It settles \(t\) , then \(b\) . Relaxing \((b,a)\) now offers \(5-4=1<2\) , but \(a\) is already settled. If the algorithm ignores the offer it reports \(d(a)=2\) and \(d(t)=3\) , both wrong. If it lowers \(\rho(a)\) to \(1\) anyway, the label of \(t\) , computed from the old value, is still wrong unless \(a\) is processed again, and then nothing remains of the guarantee that each node is handled once.
A tempting repair is to add \(4\) to every length so that all become nonnegative. The lengths become \(c_{sa}=6\) , \(c_{sb}=9\) , \(c_{ba}=0\) , \(c_{at}=5\) , and the shortest path to \(a\) is now the direct arc, of length \(6\) , since the detour costs \(9\) . The shift changed the answer. It adds \(4\) per arc, so it penalizes paths with more arcs, and the two candidate paths to \(a\) have different numbers of arcs.
Common mistake. Running Dijkstra’s algorithm on a network with negative lengths, or shifting all lengths by a constant to remove them. The proof of Theorem 2.4 needs every arc on the unexplored remainder of a path to be nonnegative, and a uniform shift does not preserve which path is shortest. A shift that does preserve shortest paths replaces \(c_{vw}\) by the slack \(c_{vw}+\pi_v-\pi_w\) for a feasible potential \(\pi\) , which changes the length of every path between two fixed nodes by the same amount; but finding such a potential already requires the method below.
The method that tolerates negative lengths gives up the idea of settling nodes and instead limits the number of arcs a walk may use.
Theorem 2.5 (Bellman–Ford recursion). Define \(d_0(s)=0\) , \(d_0(v)=\infty\) for \(v\ne s\) , and for \(k\ge 1\)
Then \(d_k(w)\) is the minimum length of a walk from \(s\) to \(w\) with at most \(k\) arcs. If no cycle reachable from \(s\) has negative length, then \(d_{n-1}=d\) . Moreover, a negative cycle is reachable from \(s\) if and only if \(d_n\ne d_{n-1}\) .
Proof. The first claim holds for \(k=0\) . A walk to \(w\) with at most \(k\) arcs either has at most \(k-1\) arcs, or consists of a walk with at most \(k-1\) arcs to some node \(v\) followed by the arc \((v,w)\) ; minimizing over the two cases and over \(v\) gives the recursion.
If no reachable cycle is negative, Lemma 2.2 says the minimum over all walks is attained by a path, and a path has at most \(n-1\) arcs, so \(d_{n-1}=d\) and one further round changes nothing. Conversely, suppose \(d_n=d_{n-1}\) . Then for every arc \((v,w)\) between reachable nodes, \(d_{n-1}(w)=d_n(w)\le d_{n-1}(v)+c_{vw}\) , with all terms finite because a reachable node is reached by a path with at most \(n-1\) arcs. Adding these inequalities around any cycle of reachable nodes, the labels cancel and the length of the cycle is seen to be nonnegative.
The recursion is the principle of optimality of dynamic programming applied to walks, with the number of arcs allowed playing the role of the stage (math.dynamic-programming-and-optimal-control.finite-horizon-bellman). Each round examines every arc once, so \(n\)
rounds take \(O(nm)\)
steps: slower than Dijkstra’s algorithm, and valid without any sign condition.
Example 2.3: Four rounds, and a fifth that reveals a negative cycle
Take the nodes \(s,a,b,c,t\) and the lengths
Each row of the table is computed from the row above by the recursion.
| \(k\) | \(d_k(a)\) | \(d_k(b)\) | \(d_k(c)\) | \(d_k(t)\) |
|---|---|---|---|---|
| \(0\) | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) |
| \(1\) | \(4\) | \(6\) | \(\infty\) | \(\infty\) |
| \(2\) | \(3\) | \(6\) | \(7\) | \(10\) |
| \(3\) | \(3\) | \(6\) | \(6\) | \(9\) |
| \(4\) | \(3\) | \(6\) | \(6\) | \(8\) |
In round 2, \(d_2(a)=\min\{4,\ 6-3\}=3\) , \(d_2(c)=\min\{4+3,\ 6+5\}=7\) , and \(d_2(t)=4+6=10\) ; these use the round-1 labels, not each other. In round 3 the improved label of \(a\) reaches \(c\) , giving \(3+3=6\) , and \(t\) improves to \(\min\{3+6,\ 7+2\}=9\) . In round 4, \(t\) improves to \(6+2=8\) . A fifth round changes nothing, so there is no negative cycle and \(d=(3,6,6,8)\) for \((a,b,c,t)\) . The shortest path to \(t\) is \(s,b,a,c,t\) , with length \(6-3+3+2=8\) ; it has four arcs, the largest number a path on five nodes can have, which is why all \(n-1=4\) rounds were needed.
Now add one arc \((c,b)\) of length \(-3\) . The cycle \(b,a,c,b\) has length \(-3+3-3=-3\) . Rounds 1 and 2 are as before. Round 3 gives \(d_3=(3,4,6,9)\) , round 4 gives \(d_4=(1,3,6,8)\) , and round 5 gives \(d_5=(0,3,4,7)\) . Since \(d_5\ne d_4\) with \(n=5\) , Theorem 2.5 reports a reachable negative cycle. The labels would go on decreasing for ever, and no shortest walk exists.
2.4 Acyclic networks and longest paths
In a network without cycles the nodes can be listed in a topological order, in which every arc points from an earlier node to a later one; this is a standard fact about directed acyclic graphs. Processing the nodes in that order and relaxing the arcs leaving each one computes all distances in a single pass of \(O(n+m)\) steps, whatever the signs of the lengths, because when a node is processed every walk into it has already been accounted for.
Because signs do not matter, the same pass computes longest paths in an acyclic network: negate the lengths, or replace each minimum by a maximum. This is special to acyclic networks. In a network with cycles, finding a longest path without repeated nodes contains the Hamiltonian path problem and is NP-hard; the argument of Lemma 2.2 does not survive negation, because it would need every cycle to have nonpositive length.
Example 2.4: The critical path of a small project
A project has five tasks with durations in days: \(A\) takes \(3\) , \(B\) takes \(2\) , \(C\) takes \(4\) , \(D\) takes \(2\) , and \(E\) takes \(3\) . Task \(C\) needs \(A\) finished; \(D\) needs both \(A\) and \(B\) ; \(E\) needs both \(C\) and \(D\) . How soon can the project finish?
Let \(F(X)\) be the earliest finish time of task \(X\) . A task starts when the last of its prerequisites finishes, so \(F(X)\) is its duration plus the largest \(F\) among its prerequisites. Taking the tasks in the topological order \(A,B,C,D,E\) :
The project needs \(10\) days, and the chain \(A,C,E\) that attains the maximum at each step is the critical path: delaying any of its tasks delays the project. Task \(D\) finishes at day \(5\) and is not needed until day \(7\) , so it has two days of slack. This is a longest-path computation in the acyclic network whose arcs are the precedence relations, and it took one evaluation per task.
2.5 Distances as a linear programming dual
Send one unit of flow from \(s\) to \(t\) at minimum cost. With a variable \(x_{vw}\ge 0\) for the amount on each arc, the problem is the linear program
A path from \(s\)
to \(t\)
gives a feasible solution, with \(x_{vw}=1\)
on its arcs and zero elsewhere, whose cost is the length of the path. Its dual, in the sense of linear programming duality from Continuous Optimization (math.continuous-optimization.linear-programming-vertices-duality), has one variable per node and one constraint per arc. After a change of sign in the dual variables it reads
The dual feasible solutions are the feasible potentials of Theorem 2.3, up to the additive constant \(\pi_s\) .
Proposition 2.6 (the path linear program has an integral optimum). Suppose every node is reachable from \(s\) and no cycle has negative length. Then a shortest path from \(s\) to \(t\) is an optimal solution of the linear program above, the distances are an optimal dual solution, and both optimal values equal \(d(t)\) .
Proof. The path solution is primal feasible with cost \(d(t)\) . The distances are dual feasible by Theorem 2.3, with objective value \(d(t)-d(s)=d(t)\) . Weak duality says that every dual feasible value is at most every primal feasible cost; a primal and a dual solution with equal values are therefore both optimal.
Two features of this small result deserve attention, because they are the template for Chapters 3, 4, and 6. The linear program was not told that \(x\) must be an integer vector, and yet it has an optimal solution with entries \(0\) and \(1\) . And complementary slackness has a combinatorial reading: an arc can carry flow in an optimal solution only if its dual constraint is tight, which says that shortest paths use only arcs of zero slack, as Figure 2.1 showed.
2.6 Minimum-cost flows
The one-unit problem is the simplest member of a family that includes most of the network models used in practice.
Definition 2.7 (minimum-cost flow problem). Let \(G=(V,A)\) be a network with costs \(c_{vw}\) , capacities \(u_{vw}\ge 0\) , and supplies \(b_v\) at the nodes with \(\sum_{v\in V}b_v=0\) . A feasible flow is a vector \(x\) with \(0\le x_{vw}\le u_{vw}\) on every arc and
The minimum-cost flow problem asks for a feasible flow minimizing \(\sum_{(v,w)\in A}c_{vw}x_{vw}\) .
A node with \(b_v>0\) is a source of that many units, a node with \(b_v<0\) is a sink, and the equations, called flow conservation, say that what enters a node plus what it supplies equals what leaves. Shortest paths are the case \(b_s=1\) , \(b_t=-1\) with unlimited capacities. A transportation problem, with factories on one side and warehouses on the other, is the case in which every arc runs from a source to a sink. The maximum-flow problem of the next chapter is the case with zero costs in which the amount shipped is itself the objective.
The potential certificate extends to flows with capacities. The slack of an arc is now called its reduced cost, and it may be negative, provided the arc is full.
Theorem 2.8 (reduced-cost optimality conditions). Let \(x\) be a feasible flow and suppose there is a potential \(\pi:V\to\mathbb R\) such that the reduced costs \(\bar c_{vw}=c_{vw}+\pi_v-\pi_w\) satisfy
for every arc. Then \(x\) is a minimum-cost flow.
Proof. Let \(x'\) be any feasible flow. Grouping the terms of \(\sum_{(v,w)}(\pi_v-\pi_w)x'_{vw}\) by node, the coefficient of \(\pi_v\) is the flow out of \(v\) minus the flow into \(v\) , which is \(b_v\) . Hence
and the last sum is the same for every feasible flow. So the costs of \(x'\) and \(x\) differ by \(\sum_{(v,w)}\bar c_{vw}(x'_{vw}-x_{vw})\) . Each term of this sum is nonnegative: where \(\bar c_{vw}>0\) we have \(x_{vw}=0\le x'_{vw}\) ; where \(\bar c_{vw}<0\) we have \(x_{vw}=u_{vw}\ge x'_{vw}\) ; and where \(\bar c_{vw}=0\) the term vanishes. Therefore the cost of \(x'\) is at least the cost of \(x\) .
The converse also holds: every minimum-cost flow admits such a potential. That direction is the strong duality theorem for linear programs applied to this problem, with the conditions above being complementary slackness, and it is not proved again here.
Example 2.5: Certifying a minimum-cost flow
Four units must be shipped from \(s\) to \(t\) through two intermediate nodes. The arcs, with cost per unit and capacity, are
There are three routes: \(s,a,b,t\) at cost \(3\) per unit, \(s,b,t\) at cost \(5\) , and \(s,a,t\) at cost \(6\) . The cheapest route can carry only \(2\) units, because of the arc \((a,b)\) . Send \(2\) units along it and the other \(2\) along \(s,b,t\) :
at total cost \(2\cdot 1+2\cdot 4+2\cdot 1+0+4\cdot 1=16\) . Conservation holds: node \(a\) receives \(2\) and sends \(2\) ; node \(b\) receives \(2+2\) and sends \(4\) .
Is \(16\) optimal? Look for a potential. Arcs carrying flow strictly between zero and capacity must have reduced cost zero. The arc \((s,a)\) carries \(2\) of \(3\) , so with \(\pi_s=0\) we need \(\pi_a=1\) ; the arc \((s,b)\) carries \(2\) of \(3\) , so \(\pi_b=4\) . The arc \((b,t)\) is full, so its reduced cost \(1+4-\pi_t\) must be at most zero, and the arc \((a,t)\) is empty, so its reduced cost \(5+1-\pi_t\) must be at least zero: any \(\pi_t\) between \(5\) and \(6\) will do. Take \(\pi=(0,1,4,5)\) for \((s,a,b,t)\) . The reduced costs are
The one negative reduced cost is on \((a,b)\) , which is full; the one positive reduced cost is on \((a,t)\) , which is empty. Theorem 2.8 applies and the flow is optimal with cost \(16\) .
The potential also prices the bottleneck. The reduced cost \(-2\) on the full arc \((a,b)\) says that one more unit of capacity there would lower the total cost by \(2\) : a unit now travelling \(s,b\) at cost \(4\) would travel \(s,a,b\) at cost \(2\) .
The theorem tells us how to recognize an optimal flow and leaves open how to find one. The standard methods start from any feasible flow and repeatedly reroute flow around a cycle along which the total cost of the change is negative, until a potential exists. Rerouting requires a precise language for how a flow may be changed, including the possibility of withdrawing flow already placed on an arc. That language, the residual network, is the main tool of the next chapter, where it is developed for the problem of sending as much flow as possible.
Exercises
-
Run Dijkstra’s algorithm from \(s\) on the network with arcs and lengths \((s,a):7\) , \((s,b):3\) , \((b,a):2\) , \((a,c):1\) , \((b,c):6\) , \((b,d):8\) , \((c,d):1\) , \((c,e):7\) , \((d,e):2\) ; give the table of labels after each node is settled, the distances, and the shortest path to \(e\) .
Solution
Labels after each node is settled, in the order in which nodes are settled:
Settled \(\rho(a)\) \(\rho(b)\) \(\rho(c)\) \(\rho(d)\) \(\rho(e)\) \(s\) \(7\) \(3\) \(\infty\) \(\infty\) \(\infty\) \(b\) \(5\) \(3\) \(9\) \(11\) \(\infty\) \(a\) \(5\) \(3\) \(6\) \(11\) \(\infty\) \(c\) \(5\) \(3\) \(6\) \(7\) \(13\) \(d\) \(5\) \(3\) \(6\) \(7\) \(9\) \(e\) \(5\) \(3\) \(6\) \(7\) \(9\) After \(s\) the smallest unsettled label is \(\rho(b)=3\) . Settling \(b\) relaxes \((b,a)\) to \(3+2=5\) , \((b,c)\) to \(9\) , and \((b,d)\) to \(11\) . Settling \(a\) lowers \(c\) to \(5+1=6\) . Settling \(c\) lowers \(d\) to \(6+1=7\) and sets \(e\) to \(13\) . Settling \(d\) lowers \(e\) to \(7+2=9\) . The distances are \(d(a)=5\) , \(d(b)=3\) , \(d(c)=6\) , \(d(d)=7\) , \(d(e)=9\) . The predecessors are \(b\) for \(a\) , \(a\) for \(c\) , \(c\) for \(d\) , and \(d\) for \(e\) , so the shortest path to \(e\) is \(s,b,a,c,d,e\) with length \(3+2+1+1+2=9\) . It uses five arcs, more than any other route, which shows that fewer arcs does not mean shorter.
-
For the network of Exercise 1, compute the slack \(c_{vw}+d(v)-d(w)\) of each of the nine arcs, identify the arcs of the shortest-path tree from the slacks alone, and use the slacks to find the length of the walk \(s,a,c,e\) without adding its arc lengths.
Answer
Slacks: \((s,a):2\) , \((s,b):0\) , \((b,a):0\) , \((a,c):0\) , \((b,c):3\) , \((b,d):4\) , \((c,d):0\) , \((c,e):4\) , \((d,e):0\) . The five arcs of slack zero form the tree \(s,b,a,c,d,e\) . The walk \(s,a,c,e\) has slacks \(2+0+4=6\) , so its length is \(d(e)+6=15\) , which agrees with \(7+1+7\) .
-
Prove that if \(s=v_0,v_1,\dots,v_k=t\) is a shortest path in a network with no negative cycle, then for all \(0\le i<j\le k\) the stretch \(v_i,\dots,v_j\) is a shortest path from \(v_i\) to \(v_j\) .
Solution
Suppose some stretch \(Q=v_i,\dots,v_j\) of the shortest path \(P\) is not a shortest path from \(v_i\) to \(v_j\) , so there is a path \(Q'\) from \(v_i\) to \(v_j\) that is strictly shorter than \(Q\) . Replace \(Q\) by \(Q'\) inside \(P\) . The result is a walk \(W\) from \(s\) to \(t\) : it follows \(P\) to \(v_i\) , then \(Q'\) to \(v_j\) , then \(P\) to \(t\) . Its length is the length of \(P\) minus the length of \(Q\) plus the length of \(Q'\) , which is strictly less than the length of \(P\) .
The walk \(W\) may repeat nodes, because \(Q'\) may pass through nodes of \(P\) outside the stretch. This is where the hypothesis is needed. By Lemma 2.2, since no cycle has negative length, some path from \(s\) to \(t\) is no longer than \(W\) . That path is strictly shorter than \(P\) , contradicting the assumption that \(P\) is a shortest path. Hence every stretch of \(P\) is a shortest path between its endpoints. Without the hypothesis the statement is false: with a negative cycle available, a shorter walk need not yield a shorter path.
-
Run the Bellman–Ford recursion from \(s\) on the network with arcs \((s,a):3\) , \((s,b):5\) , \((b,a):-4\) , \((a,c):2\) , \((c,b):3\) ; give the table \(d_k\) for \(k=0,\dots,4\) , the distances, and the evidence that there is no negative cycle.
Solution
There are \(n=4\) nodes, so three rounds suffice if there is no negative cycle, and a fourth round tests for one.
\(k\) \(d_k(a)\) \(d_k(b)\) \(d_k(c)\) \(0\) \(\infty\) \(\infty\) \(\infty\) \(1\) \(3\) \(5\) \(\infty\) \(2\) \(1\) \(5\) \(5\) \(3\) \(1\) \(5\) \(3\) \(4\) \(1\) \(5\) \(3\) Round 2 uses the round-1 labels: \(d_2(a)=\min\{3,\ 5-4\}=1\) and \(d_2(c)=3+2=5\) ; the label of \(b\) cannot improve because \(d_1(c)=\infty\) . Round 3: \(d_3(c)=1+2=3\) , and \(d_3(b)=\min\{5,\ 5+3\}=5\) . Round 4: \(d_4(b)=\min\{5,\ 3+3\}=5\) , and nothing changes. Because \(d_4=d_3\) , Theorem 2.5 certifies that no negative cycle is reachable, and the distances are \(d(a)=1\) , \(d(b)=5\) , \(d(c)=3\) . The only cycle is \(a,c,b,a\) , of length \(2+3-4=1\) , which is indeed nonnegative. The shortest path to \(c\) is \(s,b,a,c\) with length \(5-4+2=3\) .
-
In the network of Exercise 4 the length of the arc \((c,b)\) is changed from \(3\) to \(1\) . Identify the negative cycle and its length, and show by continuing the table that \(d_4\ne d_3\) .
Answer
The cycle \(a,c,b,a\) now has length \(2+1-4=-1\) . Rounds 1 to 3 are unchanged, giving \(d_3=(1,5,3)\) for \((a,b,c)\) . In round 4, \(d_4(b)=\min\{5,\ 3+1\}=4\) , so \(d_4=(1,4,3)\ne d_3\) and a reachable negative cycle is reported.
-
A student claims that the labels \(\rho(a)=4\) , \(\rho(b)=2\) , \(\rho(c)=8\) , \(\rho(d)=9\) , \(\rho(t)=12\) with \(\rho(s)=0\) are the distances in the network of Example 2.1. Use Theorem 2.3 to explain what is and is not wrong with this labelling, naming the condition of the theorem that fails.
Solution
Compare with the true distances \(d(a)=3\) , \(d(b)=2\) , \(d(c)=8\) , \(d(d)=9\) , \(d(t)=12\) found in Example 2.1: only the label of \(a\) differs.
Theorem 2.3 has two conditions. The second, that each label is the length of some walk from \(s\) , holds for the student’s labelling: \(\rho(a)=4\) is the length of the walk consisting of the single arc \((s,a)\) , and the other labels are lengths of the tree paths. So every label is an upper bound on the true distance.
The first condition, \(\rho(w)\le\rho(v)+c_{vw}\) on every arc, fails on the arc \((b,a)\) : it requires \(\rho(a)\le\rho(b)+c_{ba}=2+1=3\) , and \(\rho(a)=4\) . So \(\rho\) is not a feasible potential and the theorem gives no lower bounds from it. The violated inequality itself points to the repair: the walk \(s,b,a\) has length \(3\) . Interestingly the label \(\rho(c)=8\) is correct even though it is the length of the walk \(s,b,a,c\) , which passes through \(a\) at cost \(3\) ; the labelling is inconsistent, which is another way of seeing that it cannot be a set of distances.
-
Prove that if \(\pi\) is a feasible potential then replacing every length \(c_{vw}\) by \(c_{vw}+\pi_v-\pi_w\) changes the length of every walk from \(v\) to \(w\) by the same amount \(\pi_v-\pi_w\) , and deduce that the two networks have the same shortest paths between every pair of nodes.
Solution
Let \(v=v_0,v_1,\dots,v_k=w\) be a walk. Its new length is
\[ \sum_{i=1}^{k}\bigl(c_{v_{i-1}v_i}+\pi_{v_{i-1}}-\pi_{v_i}\bigr)=\sum_{i=1}^{k}c_{v_{i-1}v_i}+\pi_{v_0}-\pi_{v_k}, \]because the potential terms telescope. So the new length is the old length plus \(\pi_v-\pi_w\) , an amount that depends only on the endpoints and not on the walk.
Fix two nodes \(v\) and \(w\) . Every walk from \(v\) to \(w\) has its length changed by the same constant, so the order of the walks by length is the same in both networks, and a walk is shortest in one exactly when it is shortest in the other. For a cycle the endpoints coincide and the constant is zero, so cycle lengths, and in particular the absence of negative cycles, are also unchanged. Feasibility of \(\pi\) was not needed for the identity; it is what makes the new lengths nonnegative, which is the reason for making the change: Dijkstra’s algorithm can then be applied to the new network.
-
Let all lengths be nonnegative, and let the nodes be settled by Dijkstra’s algorithm in the order \(v_1,v_2,\dots,v_n\) . Prove that \(d(v_1)\le d(v_2)\le\dots\le d(v_n)\) , and point to the step of your proof that fails if some arc has negative length.
Solution
Fix \(i<n\) and consider the moment \(v_i\) is chosen. Both \(v_i\) and \(v_{i+1}\) are unsettled then, and \(v_i\) has the smallest label, so \(\rho(v_i)\le\rho(v_{i+1})\) at that moment. By Theorem 2.4, \(\rho(v_i)=d(v_i)\) .
Between that moment and the moment \(v_{i+1}\) is chosen, the only arcs relaxed are those leaving \(v_i\) . So the final label of \(v_{i+1}\) is either its label at the earlier moment, which is at least \(d(v_i)\) , or \(d(v_i)+c_{v_iv_{i+1}}\) , which is at least \(d(v_i)\) because the length is nonnegative. By Theorem 2.4 again the final label of \(v_{i+1}\) is \(d(v_{i+1})\) . Hence \(d(v_i)\le d(v_{i+1})\) .
The step that fails for negative lengths is the inequality \(d(v_i)+c_{v_iv_{i+1}}\ge d(v_i)\) . With a negative arc, a node settled later can receive a label smaller than that of a node settled earlier, and the outward sweep that the algorithm relies on is no longer monotone.
-
A project has tasks \(P,Q,R,S,T,U\) with durations \(2,4,3,5,1,2\) days; \(R\) requires \(P\) ; \(S\) requires \(P\) and \(Q\) ; \(T\) requires \(R\) and \(S\) ; \(U\) requires \(S\) . Compute the earliest finish time of every task, the project duration, a critical path, and the slack of task \(R\) .
Answer
Earliest finish times: \(F(P)=2\) , \(F(Q)=4\) , \(F(R)=2+3=5\) , \(F(S)=\max\{2,4\}+5=9\) , \(F(T)=\max\{5,9\}+1=10\) , \(F(U)=9+2=11\) . The project takes \(11\) days and the critical path is \(Q,S,U\) . Task \(R\) is needed only by \(T\) , which may finish as late as day \(11\) and so start as late as day \(10\) ; \(R\) finishes at day \(5\) , so its slack is \(5\) days.
-
Explain what is wrong with the following argument: “To find the longest path from \(s\) to \(t\) without repeated nodes in a network with positive lengths, negate all lengths and run the Bellman–Ford recursion, which handles negative lengths.”
Hint
After negation every cycle of the original network becomes a negative cycle. Look at what Theorem 2.5 computes: shortest walks with a bounded number of arcs, and walks may repeat nodes. With negative cycles present, Lemma 2.2 no longer converts walks into paths. The recursion would report a negative cycle, not a longest path. In an acyclic network the objection disappears, which is Section 2.4.
-
Write out the linear program of Section 2.5 and its dual for the network of Example 2.2, and verify Proposition 2.6 by giving a primal solution and a dual solution of equal value.
Answer
Primal: minimize \(2x_{sa}+5x_{sb}-4x_{ba}+x_{at}\) subject to \(x_{sa}+x_{sb}=1\) at \(s\) , \(x_{at}-x_{sa}-x_{ba}=0\) at \(a\) , \(x_{ba}-x_{sb}=0\) at \(b\) , \(-x_{at}=-1\) at \(t\) , and \(x\ge 0\) . Dual: maximize \(\pi_t-\pi_s\) subject to \(\pi_a-\pi_s\le 2\) , \(\pi_b-\pi_s\le 5\) , \(\pi_a-\pi_b\le -4\) , \(\pi_t-\pi_a\le 1\) . The path \(s,b,a,t\) gives \(x_{sb}=x_{ba}=x_{at}=1\) with cost \(5-4+1=2\) . The distances \(\pi=(0,1,5,2)\) for \((s,a,b,t)\) satisfy the four dual constraints, three of them with equality, and give the value \(2\) .
-
In Example 2.5, verify with Theorem 2.8 whether the flow \(x_{sa}=3\) , \(x_{sb}=1\) , \(x_{ab}=2\) , \(x_{at}=1\) , \(x_{bt}=3\) is optimal; if no potential can exist, find a cheaper feasible flow and say which condition would have to fail.
Solution
The proposed flow is feasible: node \(a\) receives \(3\) and sends \(2+1\) ; node \(b\) receives \(1+2\) and sends \(3\) . Its cost is \(3\cdot 1+1\cdot 4+2\cdot 1+1\cdot 5+3\cdot 1=17\) , which already exceeds the cost \(16\) of the flow in Example 2.5, so it is not optimal. It is instructive to see Theorem 2.8 refuse to certify it.
Normalize \(\pi_s=0\) . Arcs carrying flow strictly between zero and capacity need reduced cost zero. The arc \((s,b)\) carries \(1\) of \(3\) , so \(\pi_b=4\) . The arc \((b,t)\) carries \(3\) of \(4\) , so \(1+4-\pi_t=0\) and \(\pi_t=5\) . The arc \((a,t)\) carries \(1\) of \(2\) , so \(5+\pi_a-5=0\) and \(\pi_a=0\) . But the arc \((s,a)\) is full, which requires its reduced cost \(1+0-\pi_a=1\) to be at most zero. That fails, so no potential satisfies the conditions.
The failed condition identifies the improvement. The arc \((s,a)\) is full with a positive reduced cost, so it carries too much: move one unit from the route \(s,a,t\) , which costs \(6\) , to the route \(s,b,t\) , which costs \(5\) . The result is the flow of Example 2.5, with cost \(16\) .
-
In Example 2.5 the demand rises from \(4\) to \(5\) units. Find a feasible flow by extending the one in the example, compute its cost, and certify its optimality with a potential.
Solution
The flow of Example 2.5 uses \((s,a)\) at \(2\) of \(3\) , \((s,b)\) at \(2\) of \(3\) , \((a,b)\) at \(2\) of \(2\) , \((a,t)\) at \(0\) of \(2\) , and \((b,t)\) at \(4\) of \(4\) . A fifth unit cannot end on \((b,t)\) , which is full, so it must arrive on \((a,t)\) , and it must reach \(a\) on \((s,a)\) . The new flow is
\[ x_{sa}=3,\quad x_{sb}=2,\quad x_{ab}=2,\quad x_{at}=1,\quad x_{bt}=4, \]with cost \(3+8+2+5+4=22\) . For a potential, take \(\pi_s=0\) . The arc \((s,b)\) carries \(2\) of \(3\) , so \(\pi_b=4\) . The arc \((a,t)\) carries \(1\) of \(2\) , so \(\pi_t=\pi_a+5\) . The full arc \((s,a)\) needs \(1-\pi_a\le 0\) ; the full arc \((a,b)\) needs \(1+\pi_a-4\le 0\) ; the full arc \((b,t)\) needs \(5-\pi_t\le 0\) . All hold with \(\pi_a=1\) and \(\pi_t=6\) : the reduced costs are \(0\) , \(0\) , \(-2\) , \(0\) , and \(-1\) for the arcs in the order listed, negative only on full arcs. By Theorem 2.8 the flow is optimal with cost \(22\) . The fifth unit cost \(6\) , more than the average of the first four, because the cheap routes were exhausted.
-
Show that the shortest-path problem with nonnegative integer lengths at most \(C\) can be solved by breadth-first search after replacing each arc by a chain of unit-length arcs, state the running time in terms of \(m\) and \(C\) , and classify that running time using the definitions of Chapter 1.
Answer
An arc of length \(c_{vw}\ge 1\) becomes a chain of \(c_{vw}\) unit arcs through \(c_{vw}-1\) new nodes; arcs of length zero are handled by merging their endpoints’ labels or kept as zero-length arcs processed first. The expanded network has at most \(mC\) arcs, and breadth-first search takes \(O(mC)\) steps. This is pseudo-polynomial: polynomial in \(m\) and in the magnitude \(C\) , exponential in the encoding length \(\langle C\rangle\) . Dijkstra’s algorithm, at \(O(n^2)\) , does not depend on \(C\) at all.
-
A currency trader can convert currency \(i\) into currency \(j\) at a rate \(r_{ij}>0\) . Show how to detect whether some cyclic sequence of conversions multiplies the starting amount by a factor greater than one, by defining suitable arc lengths and using Theorem 2.5.
Hint
A cycle of conversions multiplies the amount by the product of its rates. Take logarithms to turn the product into a sum, and choose the sign so that “product greater than one” becomes “sum less than zero”: \(c_{ij}=-\log r_{ij}\) . Theorem 2.5 detects negative cycles reachable from the source, so add an artificial source joined to every currency by an arc of length zero.
-
Prove that the predecessor records at the end of Dijkstra’s algorithm, taken over all reachable nodes other than \(s\) , form a tree in which the path from \(s\) to each node \(v\) has length \(d(v)\) .
Hint
Each reachable node other than \(s\) has exactly one predecessor, and the predecessor of a node was settled before the node was. Following predecessors therefore moves strictly backwards in the settling order and must end at \(s\) , so there are no cycles and the records form a tree with \(n-1\) arcs on the reachable nodes. For the length, the label of \(w\) was last set to \(\rho(v)+c_{vw}\) with \(v\) its predecessor, and both labels are distances by Theorem 2.4; induct along the tree path.
-
The integer program “minimize \(\sum c_{vw}x_{vw}\) subject to the flow conservation equations of Section 2.5 and \(x_{vw}\in\{0,1\}\) ” has exponentially many feasible solutions in general. Using Proposition 1.3 and Proposition 2.6, explain why its relaxation nevertheless solves it exactly when lengths are nonnegative.
Hint
The relaxation is the linear program of Section 2.5 with the extra bounds \(x_{vw}\le 1\) , which a path solution satisfies. Proposition 2.6 exhibits an optimal solution of the relaxation with entries \(0\) and \(1\) . Apply the minimization form of Proposition 1.3: an integral optimum of the relaxation is optimal for the integer program.
-
Dijkstra’s algorithm, in the form that never changes the label of a settled node, is run on the network of Example 2.1 after the arc \((b,a)\) is removed and an arc \((a,b)\) of length \(-3\) is added. State the labels it reports, the true distances, and the step at which the argument in the proof of Theorem 2.4 breaks down.
Solution
The modified network has lengths \(c_{sa}=4\) , \(c_{sb}=2\) , \(c_{ab}=-3\) , \(c_{ac}=5\) , \(c_{bc}=8\) , \(c_{bd}=7\) , \(c_{cd}=2\) , \(c_{ct}=6\) , \(c_{dt}=3\) , and it has no cycle, so distances exist.
What the algorithm does. Settling \(s\) gives \(\rho(a)=4\) and \(\rho(b)=2\) . It settles \(b\) and sets \(\rho(c)=10\) , \(\rho(d)=9\) . It settles \(a\) , lowering \(\rho(c)\) to \(9\) ; the arc \((a,b)\) offers \(4-3=1\) , but \(b\) is settled and its label stays \(2\) . It settles \(c\) , which offers \(d\) the value \(11\) and sets \(\rho(t)=15\) ; then \(d\) , lowering \(\rho(t)\) to \(12\) . The reported labels are \((4,2,9,9,12)\) for \((a,b,c,d,t)\) .
The truth. The path \(s,a,b\) has length \(4-3=1\) , so \(d(b)=1\) , and then \(d(d)=1+7=8\) and \(d(t)=8+3=11\) ; \(d(a)=4\) and \(d(c)=9\) are as reported. The true distances are \((4,1,9,8,11)\) .
Where the proof breaks. When \(b\) was settled with label \(2\) , the proof of Theorem 2.4 considered an arbitrary path to \(b\) , here \(s,a,b\) , found its first unsettled node \(a\) with \(\rho(a)=4\) , and claimed that the remainder of the path, the arc \((a,b)\) , has nonnegative length, so that the path is at least as long as \(4\ge 2\) . The remainder has length \(-3\) and the claim is false.