Why Topological Order Helps
Shortest-path algorithms that repeatedly revisit edges can handle many kinds of weighted directed graphs. A directed acyclic graph (DAG) has a simpler structure: every directed path moves forward in a topological ordering. This lets us process each vertex once, after all its possible predecessors have been processed. Edge weights may be negative; the absence of directed cycles means there is no route that can loop around and reduce its cost indefinitely.
Throughout, graphs are finite and simple. A weighted digraph is a directed graph whose edges have real-valued weights \(w(u,v)\). A directed path from \(s\) to \(v\) is a sequence of vertices beginning at \(s\), ending at \(v\), and following directed edges; its cost is the sum of their weights. The length-zero path from \(s\) to itself has cost \(0\). A vertex is reachable from \(s\) if there is a directed path from \(s\) to it. The distance \(d(s,v)\) is the minimum cost of such a path when one exists, and is \(+\infty\) otherwise.
In a finite DAG every directed path has no repeated vertices, so there are only finitely many such paths. Consequently, if \(v\) is reachable from \(s\), a minimum-cost path to \(v\) exists, even if some weights are negative. If \(v\) is unreachable, its distance is \(+\infty\). We use \(+\infty\) as a label meaning “no path found”; the algorithm skips relaxation from a vertex with this label.
The Topological-Order Relaxation Algorithm
For each vertex \(v\), keep a distance label \(D(v)\). Also keep a predecessor pointer \(\pi(v)\), initially empty, to record the last vertex on a path that attains the current label. To relax an edge \(u\to v\) of weight \(w(u,v)\), compare the candidate \(D(u)+w(u,v)\) with \(D(v)\). If \(D(u)\) is finite and the candidate is smaller, replace \(D(v)\) by that candidate and set \(\pi(v)=u\). If the candidate equals the current label, either predecessor may be retained.
Set \(D(s)=0\), set \(D(v)=+\infty\) for every \(v\ne s\), and leave all predecessor pointers empty.
List every vertex so that each edge points forward in the list.
For each vertex \(u\), relax every outgoing edge \(u\to v\). If \(D(u)=+\infty\), make no updates from \(u\).
After the list is processed, \(D(v)\) is the shortest-path distance from \(s\), or \(+\infty\) if \(v\) is unreachable. Following predecessor pointers backwards recovers a shortest path when \(v\) is reachable.
A topological ordering exists for every finite DAG. Here is a proof that also gives a way to construct one.
Proof. We use induction on the number \(n\) of vertices. If \(n=0\), the empty list is a topological ordering. Suppose \(n>0\). There must be a vertex with no incoming edge. Otherwise, starting at any vertex and repeatedly following an incoming edge backwards would, because there are only finitely many vertices, eventually repeat a vertex. The edges followed between repetitions would form a directed cycle, contradicting acyclicity. Choose a vertex \(x\) with no incoming edge and remove it. The remaining graph is still acyclic, so by induction it has a topological ordering. Place \(x\) first, followed by that ordering. No edge points into \(x\), and all edges among the remaining vertices point forward by induction; any edge out of \(x\) also points forward because \(x\) is first. This gives a topological ordering of the original graph. \(\square\)
Worked Examples
Worked Example: Negative Weights and Successive Improvements
Let the weighted digraph have vertex set \(V=\{s,a,b,c,d,t\}\) and edges \(s\to a\) of weight \(4\), \(s\to b\) of weight \(5\), \(a\to b\) of weight \(-2\), \(a\to c\) of weight \(6\), \(b\to c\) of weight \(3\), \(b\to d\) of weight \(4\), \(c\to d\) of weight \(-1\), \(c\to t\) of weight \(5\), and \(d\to t\) of weight \(2\). A topological ordering is \(s,a,b,c,d,t\). Find the distances from \(s\).
Initialize \(D(s)=0\) and \(D(a)=D(b)=D(c)=D(d)=D(t)=+\infty\). Process each vertex and relax its outgoing edges:
| Vertex processed | Relaxations and resulting labels |
|---|---|
| \(s\) | \(D(a)=0+4=4\); \(D(b)=0+5=5\). |
| \(a\) | To \(b\), candidate \(4+(-2)=2\), so \(D(b)=2\). To \(c\), candidate \(4+6=10\), so \(D(c)=10\). |
| \(b\) | To \(c\), candidate \(2+3=5\), so \(D(c)=5\). To \(d\), candidate \(2+4=6\), so \(D(d)=6\). |
| \(c\) | To \(d\), candidate \(5+(-1)=4\), so \(D(d)=4\). To \(t\), candidate \(5+5=10\), so \(D(t)=10\). |
| \(d\) | To \(t\), candidate \(4+2=6\), so \(D(t)=6\). |
| \(t\) | No outgoing edges; labels do not change. |
The final labels are \(D(s)=0\), \(D(a)=4\), \(D(b)=2\), \(D(c)=5\), \(D(d)=4\), and \(D(t)=6\). The predecessor pointers give the path \(s,a,b,c,d,t\) to \(t\). Its cost is \(4+(-2)+3+(-1)+2=6\).
Check: Substituting the final labels on the edges gives \(D(a)=D(s)+4=4\), \(D(b)=D(a)-2=2\), \(D(c)=D(b)+3=5\), \(D(d)=D(c)-1=4\), and \(D(t)=D(d)+2=6\). The other incoming candidates are no smaller: \(D(s)+5=5\) for \(b\); \(D(a)+6=10\) for \(c\); \(D(b)+4=6\) for \(d\); and \(D(c)+5=10\) for \(t\). Thus no edge offers an improvement to the reported labels.
Worked Example: Unreachable Vertices
Let \(V=\{x,s,a,b,c,z\}\) and let the weighted edges be \(x\to z\) of weight \(-8\), \(s\to a\) of weight \(2\), \(s\to b\) of weight \(7\), \(a\to b\) of weight \(-4\), \(a\to c\) of weight \(5\), and \(b\to c\) of weight \(3\). Use source \(s\) and topological order \(x,s,a,b,c,z\). Notice that the source need not be first in the ordering.
Initialize \(D(s)=0\) and all other labels to \(+\infty\). Processing \(x\) does nothing: \(D(x)=+\infty\), so its edge to \(z\) is not relaxed. Processing \(s\) sets \(D(a)=0+2=2\) and \(D(b)=0+7=7\). Processing \(a\) gives candidate \(2+(-4)=-2\) for \(b\), replacing \(7\), and candidate \(2+5=7\) for \(c\). Processing \(b\) gives candidate \(-2+3=1\) for \(c\), replacing \(7\). Processing \(c\) and then \(z\) makes no further changes.
The final distances are \(D(s)=0\), \(D(a)=2\), \(D(b)=-2\), \(D(c)=1\), and \(D(x)=D(z)=+\infty\). The predecessor pointers recover \(s,a,b,c\) as a shortest path to \(c\), with cost \(2+(-4)+3=1\).
Check: The paths to \(c\) are \(s,a,c\), of cost \(2+5=7\); \(s,b,c\), of cost \(7+3=10\); and \(s,a,b,c\), of cost \(2+(-4)+3=1\). The minimum is \(1\). The negative edge \(x\to z\) does not make \(z\) reachable from \(s\), so its distance remains \(+\infty\).
Worked Example: Tied Routes and Predecessors
Let \(V=\{r,p,q,t\}\) and let the weighted edges be \(r\to p\) of weight \(2\), \(r\to q\) of weight \(1\), \(p\to q\) of weight \(-1\), \(p\to t\) of weight \(3\), and \(q\to t\) of weight \(3\). Use the topological ordering \(r,p,q,t\) and source \(r\).
Initialize \(D(r)=0\) and the other labels to \(+\infty\). Processing \(r\) gives \(D(p)=0+2=2\) and \(D(q)=0+1=1\), with \(\pi(p)=r\) and \(\pi(q)=r\). Processing \(p\) gives candidate \(2+(-1)=1\) for \(q\), which ties its existing label, so keep \(\pi(q)=r\). The candidate for \(t\) is \(2+3=5\), so set \(D(t)=5\) and \(\pi(t)=p\). Processing \(q\) gives candidate \(1+3=4\), so replace \(D(t)=5\) by \(D(t)=4\) and set \(\pi(t)=q\). Processing \(t\) changes nothing.
The final distances are \(D(r)=0\), \(D(p)=2\), \(D(q)=1\), and \(D(t)=4\). The predecessor pointers recover \(r,q,t\), of cost \(1+3=4\).
Check: The three directed paths from \(r\) to \(t\) are \(r,p,t\), of cost \(2+3=5\); \(r,q,t\), of cost \(1+3=4\); and \(r,p,q,t\), of cost \(2+(-1)+3=4\). Thus the minimum cost is \(4\), matching the algorithm. The tie at \(q\) does not affect the distance or the validity of the recovered path.
Why the Algorithm Works
The key feature is that every edge entering a vertex \(v\) comes from a vertex earlier in the ordering. Thus, by the time \(v\) is processed, all possible last edges of paths to \(v\) have already had their starting vertices processed.
Proof. Fix a topological ordering and consider its vertices in order. Before processing a vertex \(v\), every incoming edge \(u\to v\) has its tail \(u\) earlier in the ordering, so \(u\) has already been processed. We show in order that the label of each processed vertex is its true distance. For the source \(s\), the length-zero path has cost \(0\). A different path from \(s\) back to \(s\) would contain a directed cycle, which is impossible; hence \(d(s,s)=0\). No incoming edge can give a finite candidate to \(s\): if \(u\) were reachable from \(s\) and \(u\to s\), those edges would form a directed cycle. Therefore \(D(s)=d(s,s)\).
Now let \(v\ne s\), and suppose the claim holds for every earlier vertex. If \(v\) is unreachable, no earlier reachable vertex can have an edge to \(v\), since that would make \(v\) reachable. Its label remains \(+\infty=d(s,v)\). If \(v\) is reachable, every path from \(s\) to \(v\) has a final edge \(u\to v\), where \(u\) is earlier than \(v\). Its cost is the cost of a path to \(u\) plus \(w(u,v)\). By the induction hypothesis, processing \(u\) used the correct distance \(d(s,u)\) and relaxed this edge. Taking the minimum candidate over all incoming edges therefore gives the minimum path cost to \(v\). No other edge can later change \(D(v)\), because any edge entering \(v\) has its tail earlier and has already been processed. Thus \(D(v)=d(s,v)\). Induction over the ordering proves the claim for every vertex. The argument uses no assumption that weights are nonnegative. \(\square\)
The running time is \(O(|V|+|E|)\): a topological ordering can be found by repeatedly removing a vertex of indegree zero and updating the indegrees of its outgoing neighbors. Each vertex is removed once, and each edge is examined a bounded number of times. The relaxation stage also processes each vertex and edge once. The algorithm stores one label and one predecessor per vertex, in addition to the graph and ordering.
Common Pitfall: Processing Vertices in the Wrong Order
Relaxing each edge once is not enough if the vertices are not processed topologically. For example, take \(V=\{s,a,b\}\) with edges \(s\to a\) of weight \(2\), \(s\to b\) of weight \(5\), and \(a\to b\) of weight \(-4\). The ordering \(s,b,a\) is invalid because the edge \(a\to b\) points backwards. If \(s\) is processed first, the labels become \(D(a)=2\) and \(D(b)=5\). Processing \(b\) next does nothing, and processing \(a\) last changes \(D(b)\) to \(2+(-4)=-2\), but \(b\)'s outgoing edges (if any) would not be processed again. In a topological order \(s,a,b\), processing \(a\) first improves \(D(b)\) to \(-2\), before \(b\) is processed. The ordering is part of the method, not an optional presentation choice.
Topological-order relaxation is useful when the input is known to be acyclic and negative edge weights are possible. It avoids the repeated passes used by Bellman–Ford, while predecessor pointers provide paths as well as distances. If the graph has a directed cycle, it has no topological ordering and this algorithm does not apply.
Check Your Understanding
For each question, specify the relevant edge weights and use the topological ordering when tracing the algorithm.
- Why does the absence of directed cycles ensure that a reachable vertex has a minimum-cost path even when some weights are negative?
- In the first worked example, what labels are present just after processing \(b\), and which outgoing edge of \(c\) later improves a label?
- For the second example, why must \(D(z)\) remain \(+\infty\) when the source is \(s\), despite the negative edge \(x\to z\)?
- Give a topological ordering for the graph with vertices \(\{u,v,w\}\) and edges \(u\to w\), \(v\to w\). Is the order unique?
- For the third example, which predecessor pointer is retained at \(q\) when the candidate from \(p\) ties its current label, and why is that pointer still valid?