Why the Processing Order Matters
In a directed graph, a path can reach a vertex only by following the direction of its edges. If the graph has no directed cycles, its vertices can be ordered so that every edge points forward. This order gives a useful guarantee: when a vertex is processed, every vertex that could reach it along a path has already been processed. Relaxing its outgoing edges can therefore pass correct distance information onward without having to revisit it.
Here, a weighted directed graph is \(D=(V,A,w)\), where \(V\) is a finite vertex set, \(A\) is a set of directed edges, and \(w(u,v)\) is a real weight for each edge \((u,v)\in A\). A directed path is a sequence of distinct vertices whose consecutive pairs are edges in the stated direction; its cost is the sum of its edge weights. A path of length zero from a vertex to itself has cost zero. A directed acyclic graph (DAG) is a directed graph with no directed cycle. Fix a source vertex \(s\). Write \(\operatorname{dist}(s,v)\) for the least cost of a directed path from \(s\) to \(v\), and set it to \(\infty\) when no such path exists.
The labels are initialized by \(D(s)=0\) and \(D(v)=\infty\) for \(v\ne s\). Process vertices in a topological order; when processing \(u\), relax every edge leaving \(u\). Weights may be negative: the method relies on the absence of directed cycles, not on nonnegative weights.
Topological Orders and Finite Shortest Paths
Proof. We use induction on the number \(n\) of vertices. If \(n=0\), the empty listing is a topological order. Suppose \(n>0\). There must be a vertex with no incoming edge. Otherwise, starting at any vertex and repeatedly moving to a vertex with an edge into the current one would, by finiteness, eventually repeat a vertex. The edges followed between repetitions would form a directed cycle, contrary to the hypothesis. Remove a vertex \(x\) with no incoming edge. The remaining graph is still acyclic, so by induction it has a topological order. Put \(x\) first in that order. No edge enters \(x\), and every edge among the remaining vertices points forward in their order. Thus every edge in the original graph points forward in the new listing. \(\square\)
A second consequence of acyclicity is that shortest-path distances are well-defined, even if weights are negative. Any directed walk that repeats a vertex contains a directed cycle between two occurrences of that vertex. A DAG has no such walk. Thus every directed walk in a DAG has distinct vertices, and there are only finitely many directed paths between any two vertices. If at least one path from \(s\) to \(v\) exists, the least of their finitely many costs is attained.
Most importantly, the vertices on any directed path appear in their path order in a topological order. If the path is \(u_0,u_1,\ldots,u_k\), each edge \((u_i,u_{i+1})\) points forward, so \(u_i\) occurs before \(u_{i+1}\). This is the fact that allows distance information to travel along a whole path in one pass.
Correctness of Topological-Order Relaxation
Proof. First, any finite label assigned by the algorithm is the cost of an actual directed path from \(s\) to its vertex. Initially, the only finite label is \(D(s)=0\), the cost of the length-zero path. When relaxing \((u,v)\), a new finite candidate \(D(u)+w(u,v)\) is formed only if \(D(u)\) is finite. If that label is the cost of a path to \(u\), appending \((u,v)\) gives a directed path to \(v\) of the candidate cost. The update either keeps the old label or replaces it by such a path cost. Induction over the relaxations proves the claim. Consequently, no finite label can be less than \(\operatorname{dist}(s,v)\).
Now suppose \(v\) is reachable from \(s\), and take a path of least cost \(s=u_0,u_1,\ldots,u_k=v\). Its vertices occur in this order in the topological listing. The initial label of \(u_0=s\) is zero, equal to the cost of the path prefix of length zero. Whenever \(u_i\) is processed, its label is no greater than the cost of the path prefix from \(s\) to \(u_i\): this holds for \(i=0\), and relaxing \((u_i,u_{i+1})\) makes the next label no greater than the cost of the prefix extended by that edge. Induction along the path therefore gives \(D(v)\leq\operatorname{dist}(s,v)\) after \(u_{k-1}\) is processed. If \(k=0\), the initial label \(D(s)=0\) already gives this inequality. Labels never increase, so the inequality still holds at the end. Together with the lower bound from the first paragraph, \(D(v)=\operatorname{dist}(s,v)\).
If \(v\) is unreachable, the path-realization argument shows that it can never receive a finite label: a finite label would certify a path from \(s\) to \(v\). Its label therefore remains \(\infty\), which equals \(\operatorname{dist}(s,v)\) by definition. This proves the claim for reachable and unreachable vertices. \(\square\)
The proof also explains the algorithm’s central invariant: when a vertex is reached in the topological order, all possible path prefixes leading to it have had their edges relaxed. A later vertex cannot send a new label backward to it, because every edge points forward.
Worked Example: Negative Edges and Multiple Routes
Let \(D\) have vertices \(V=\{s,a,b,c,t\}\) and directed, weighted edges \((s,a):2\), \((s,b):5\), \((a,b):-4\), \((a,c):3\), \((b,c):2\), \((b,t):6\), and \((c,t):-1\). Use the topological order \(s,a,b,c,t\). Each listed edge points forward in this order.
Initialize \((D(s),D(a),D(b),D(c),D(t))=(0,\infty,\infty,\infty,\infty)\). Processing \(s\) relaxes \((s,a)\), giving \(D(a)=\min(\infty,0+2)=2\), and \((s,b)\), giving \(D(b)=\min(\infty,0+5)=5\). Processing \(a\) gives \(D(b)=\min(5,2+(-4))=-2\) and \(D(c)=\min(\infty,2+3)=5\). Processing \(b\) gives \(D(c)=\min(5,-2+2)=0\) and \(D(t)=\min(\infty,-2+6)=4\). Processing \(c\) gives \(D(t)=\min(4,0+(-1))=-1\). Processing \(t\) has no outgoing edges.
| Vertex processed | Labels afterward, in order \((s,a,b,c,t)\) |
|---|---|
| Initialization | \((0,\infty,\infty,\infty,\infty)\) |
| \(s\) | \((0,2,5,\infty,\infty)\) |
| \(a\) | \((0,2,-2,5,\infty)\) |
| \(b\) | \((0,2,-2,0,4)\) |
| \(c\) | \((0,2,-2,0,-1)\) |
| \(t\) | \((0,2,-2,0,-1)\) |
Check: the paths \(s,a\), \(s,a,b\), \(s,a,b,c\), and \(s,a,b,c,t\) have costs \(2\), \(2+(-4)=-2\), \(2+(-4)+2=0\), and \(2+(-4)+2+(-1)=-1\), respectively. The other route to \(b\), namely \(s,b\), costs \(5\); the route \(s,a,c\) costs \(2+3=5\); and the route \(s,a,b,t\) costs \(2+(-4)+6=4\). These agree with the final labels and show why a negative edge is not itself a problem.
Worked Example: Vertices Unreachable from the Source
Let \(D\) have vertices \(V=\{s,a,x,y,z\}\) and directed, weighted edges \((s,a):4\), \((x,y):1\), and \((y,z):3\). Use the topological order \(s,a,x,y,z\). The vertices \(x,y,z\) lie in a separate directed component, so none is reachable from \(s\).
Start with labels \((0,\infty,\infty,\infty,\infty)\), in the order \((s,a,x,y,z)\). Processing \(s\) relaxes \((s,a)\), giving \(D(a)=\min(\infty,0+4)=4\). Processing \(a\) changes no label. Processing \(x\) skips \((x,y)\) because \(D(x)=\infty\); in particular, the algorithm does not treat \(\infty+1\) as a finite candidate. Processing \(y\) likewise skips \((y,z)\) because \(D(y)=\infty\). Processing \(z\) changes no label. The final labels are \((0,4,\infty,\infty,\infty)\).
Check: the path \(s,a\) has cost \(4\), so \(D(a)=4\). There is no directed path from \(s\) to \(x\), \(y\), or \(z\), since no edge leaves the component containing \(s\) and \(a\) to reach those vertices. Thus their correct distances are all \(\infty\), as the algorithm reports.
Worked Example: Two Equal-Cost Paths
Let \(D\) have vertices \(V=\{s,p,q,r,u\}\) and directed, weighted edges \((s,p):1\), \((s,q):1\), \((p,r):2\), \((q,r):2\), \((r,u):0\), and \((p,u):2\). Use the topological order \(s,p,q,r,u\).
Initialize labels in the order \((s,p,q,r,u)\) as \((0,\infty,\infty,\infty,\infty)\). Processing \(s\) gives \(D(p)=\min(\infty,0+1)=1\) and \(D(q)=\min(\infty,0+1)=1\), so the labels are \((0,1,1,\infty,\infty)\). Processing \(p\) gives \(D(r)=\min(\infty,1+2)=3\) and \(D(u)=\min(\infty,1+2)=3\), giving \((0,1,1,3,3)\). Processing \(q\) gives \(D(r)=\min(3,1+2)=3\), so the labels do not change. Processing \(r\) gives \(D(u)=\min(3,3+0)=3\), again with no change. Processing \(u\) has no outgoing edges.
Check: the two paths \(s,p,r,u\) and \(s,q,r,u\) each cost \(1+2+0=3\), and the path \(s,p,u\) costs \(1+2=3\). Thus the final label \(D(u)=3\) agrees with each of these routes. The algorithm needs only the distance value; if a predecessor is recorded, the chosen path can depend on which equal-cost candidate is retained.
A Common Ordering Mistake
Processing vertices in an arbitrary order can leave a label too large, even when the graph is a DAG. For a concrete example, let \(V=\{s,a,b,t\}\) and let the directed, weighted edges be \((s,a):1\), \((s,b):0\), \((b,a):-2\), and \((a,t):0\). The order \(s,a,b,t\) is invalid because the edge \((b,a)\) points backward. Processing \(s\) gives \(D(a)=1\) and \(D(b)=0\). Processing \(a\) then gives \(D(t)=1+0=1\). Processing \(b\) improves \(D(a)\) to \(\min(1,0+(-2))=-2\), but \(a\) has already been processed, so its outgoing edge is not relaxed again. The algorithm ends with the incorrect label \(D(t)=1\), although the path \(s,b,a,t\) has cost \(0+(-2)+0=-2\).
The correction is to use a valid topological order, such as \(s,b,a,t\). After processing \(s\), the labels are \(D(a)=1\) and \(D(b)=0\). Processing \(b\) changes \(D(a)\) to \(\min(1,0+(-2))=-2\). Processing \(a\) then changes \(D(t)\) to \(\min(\infty,-2+0)=-2\). This matches the cost of \(s,b,a,t\). The failure was not caused by the negative weight; it was caused by processing \(a\) before the path’s preceding vertex \(b\).
Check Your Understanding
Use the topological-order argument to justify each conclusion, not just the final labels.
- In a topological order, why must the vertices of every directed path appear in the order in which the path traverses them?
- Why can a DAG with negative edge weights still have a finite shortest-path distance whenever a vertex is reachable?
- Suppose \(s\) reaches \(v\) by the path \(s=u_0,u_1,\ldots,u_k=v\). At which step of the correctness proof is the edge \((u_{k-1},v)\) relaxed?
- Give a reason that an unreachable vertex cannot receive a finite label during the algorithm.
- For the graph in the common-ordering example, compute all labels using the valid order \(s,b,a,t\).