Shortest Paths by Processing a DAG
When edge weights can be negative, Dijkstra’s algorithm is not generally reliable. A directed acyclic graph (DAG) offers another approach: process vertices in an order that places every edge’s tail before its head. By the time a vertex is processed, every possible route to it has been accounted for, so its outgoing edges can be relaxed once. This tutorial traces the method, including how to recover routes and how to handle vertices that the source cannot reach.
All graphs below are finite and directed. Each edge \(uv\) has a real weight \(w(u,v)\). A directed path from \(s\) to \(v\) is a sequence beginning at \(s\) and ending at \(v\), with each consecutive pair forming a directed edge. Its cost is the sum of its edge weights; the path of length zero from a vertex to itself has cost \(0\). A shortest path is a path of minimum cost. In a DAG, directed paths cannot repeat a vertex: a repeated vertex would give a directed cycle. Thus there are finitely many paths between any two vertices, and if at least one exists, a minimum-cost path exists even when some weights are negative.
The symbol \(\infty\) means that no route from the source has yet been found. A label that remains \(\infty\) after all vertices are processed means that the vertex is unreachable from the source. A topological order exists for every finite DAG. To see this, if a nonempty DAG had no vertex with indegree zero, repeatedly following an incoming edge would eventually revisit a vertex, producing a directed cycle. So there is a vertex with indegree zero. Remove it, order the remaining DAG by induction on the number of vertices, and place the removed vertex first. The empty graph has the empty order, which starts the induction.
The Relaxation Rule and Why It Works
Process vertices in topological order and relax all outgoing edges of each vertex. A candidate \(d(u)+w(u,v)\) is considered only when \(d(u)\ne\infty\); an unreachable vertex has no known route to extend. If two routes give the same minimum label, either predecessor gives a shortest route.
Proof. Fix a topological order and use induction along it. When a vertex \(v\) is about to be processed, every possible predecessor \(u\) of \(v\) occurs earlier, since every edge \(uv\) points forward in the order. Suppose first that \(v=s\). The zero-length path gives cost \(0\), and a different path from \(s\) back to \(s\) would contain a directed cycle, which is impossible. Thus the minimum cost to \(s\) is \(0\). No reachable predecessor can enter \(s\), for a route from \(s\) to that predecessor followed by its edge to \(s\) would also make a directed cycle.
Now take \(v\ne s\). Every path from \(s\) to \(v\), if one exists, has a last edge \(uv\). The part of the path from \(s\) to \(u\) has minimum cost \(d(u)\) when \(u\) is processed, by the induction hypothesis. Relaxing \(uv\) therefore considers the cost of a minimum-cost route through \(u\). Taking the minimum over all incoming edges considers every possible last edge and hence gives the minimum cost to \(v\). If no incoming edge can be extended from a reachable vertex, there is no path from \(s\) to \(v\), so its label remains \(\infty\). Each finite label is the cost of an actual route: it starts at \(0\), and every update extends a known route by one edge. Therefore the procedure neither misses a shorter route nor reports a cost that no route attains. \(\square\)
To reconstruct a route, start at the destination and repeatedly follow predecessor pointers backwards until reaching the source, then reverse the sequence. This is valid because a predecessor is recorded only when an edge extends a route to the vertex. When a vertex is unreachable, it has no predecessor and there is no route to reconstruct.
Worked Traces
Worked Example: Negative Edges and Several Routes
Let \(G\) have vertex set \(V=\{s,a,b,c,d,t\}\) and directed weighted edge set \(E=\{s\mathbin{\to}a:4,\ s\mathbin{\to}b:2,\ b\mathbin{\to}a:-1,\ a\mathbin{\to}c:3,\ b\mathbin{\to}c:5,\ a\mathbin{\to}d:2,\ b\mathbin{\to}d:4,\ c\mathbin{\to}d:-2,\ c\mathbin{\to}t:4,\ d\mathbin{\to}t:3\}\). The notation \(u\mathbin{\to}v:x\) means a directed edge from \(u\) to \(v\) of weight \(x\). Use the order \(s,b,a,c,d,t\). It is topological: the tail of each listed edge occurs before its head.
Initialize \(d(s)=0\) and \(d(a)=d(b)=d(c)=d(d)=d(t)=\infty\). The table gives each finite candidate and the resulting label; a predecessor is changed whenever a candidate improves a label.
| Processed vertex | Relaxations and resulting labels |
|---|---|
| \(s\) | \(s\to a:\ 0+4=4\), so \(d(a)=4\), predecessor \(s\). \(s\to b:\ 0+2=2\), so \(d(b)=2\), predecessor \(s\). |
| \(b\) | \(b\to a:\ 2+(-1)=1\), improving \(d(a)\) from \(4\) to \(1\), predecessor \(b\). \(b\to c:\ 2+5=7\), so \(d(c)=7\). \(b\to d:\ 2+4=6\), so \(d(d)=6\). |
| \(a\) | \(a\to c:\ 1+3=4\), improving \(d(c)\) from \(7\) to \(4\), predecessor \(a\). \(a\to d:\ 1+2=3\), improving \(d(d)\) from \(6\) to \(3\), predecessor \(a\). |
| \(c\) | \(c\to d:\ 4+(-2)=2\), improving \(d(d)\) from \(3\) to \(2\), predecessor \(c\). \(c\to t:\ 4+4=8\), so \(d(t)=8\), predecessor \(c\). |
| \(d\) | \(d\to t:\ 2+3=5\), improving \(d(t)\) from \(8\) to \(5\), predecessor \(d\). |
| \(t\) | No outgoing edges; no updates. |
The final labels are \(d(s)=0\), \(d(b)=2\), \(d(a)=1\), \(d(c)=4\), \(d(d)=2\), and \(d(t)=5\). Following predecessors from \(t\) gives \(t,d,c,a,b,s\); reversing produces the route \(s,b,a,c,d,t\). Its cost is \(2+(-1)+3+(-2)+3=5\).
Check: The only edges entering \(t\) are \(ct\) and \(dt\), giving route costs \(4+4=8\) and \(2+3=5\), respectively. For \(d\), the incoming-edge candidates are \(1+2=3\), \(2+4=6\), and \(4+(-2)=2\); their minimum is \(2\). Thus the final labels at \(d\) and \(t\) agree with the minimum over their incoming edges.
Worked Example: An Unreachable Vertex
Let \(G\) have vertex set \(V=\{r,u,v,w,x,z\}\) and directed weighted edge set \(E=\{r\mathbin{\to}u:3,\ r\mathbin{\to}v:8,\ u\mathbin{\to}v:-4,\ u\mathbin{\to}w:5,\ v\mathbin{\to}w:2,\ w\mathbin{\to}x:1\}\). The vertex \(z\) is isolated. Use the topological order \(r,u,v,w,x,z\), and take \(r\) as the source.
| Processed vertex | Relaxations and resulting labels |
|---|---|
| \(r\) | \(r\to u:\ 0+3=3\), so \(d(u)=3\). \(r\to v:\ 0+8=8\), so \(d(v)=8\). |
| \(u\) | \(u\to v:\ 3+(-4)=-1\), improving \(d(v)\) from \(8\) to \(-1\). \(u\to w:\ 3+5=8\), so \(d(w)=8\). |
| \(v\) | \(v\to w:\ -1+2=1\), improving \(d(w)\) from \(8\) to \(1\). |
| \(w\) | \(w\to x:\ 1+1=2\), so \(d(x)=2\). |
| \(x\) | No outgoing edges; no updates. |
| \(z\) | No incoming or outgoing edges; \(d(z)=\infty\). |
The route to \(x\) is recovered by following predecessors: \(x,w,v,u,r\), which reverses to \(r,u,v,w,x\). Its cost is \(3+(-4)+2+1=2\). The other routes to \(x\) are \(r,u,w,x\), with cost \(3+5+1=9\), and \(r,v,w,x\), with cost \(8+2+1=11\). These are all the possibilities: a route must reach \(w\) through \(u\) or \(v\), and then use \(w\to x\). The label \(d(z)=\infty\) is correct because there is no edge into \(z\), and \(z\ne r\).
Worked Example: Choosing Between Tied Initial Labels
Let \(G\) have vertex set \(V=\{p,q,r,s,t\}\) and directed weighted edge set \(E=\{p\mathbin{\to}q:2,\ p\mathbin{\to}r:2,\ q\mathbin{\to}s:3,\ r\mathbin{\to}s:1,\ q\mathbin{\to}t:7,\ r\mathbin{\to}t:4,\ s\mathbin{\to}t:1\}\). Use the topological order \(p,q,r,s,t\) and source \(p\).
Processing \(p\) gives \(d(q)=0+2=2\) and \(d(r)=0+2=2\). Processing \(q\) gives the candidate \(d(s)=2+3=5\) and \(d(t)=2+7=9\). Processing \(r\) gives \(d(s)=2+1=3\), improving \(5\), and \(d(t)=2+4=6\), improving \(9\). Finally, processing \(s\) gives \(d(t)=3+1=4\), improving \(6\). Thus the labels are \(d(p)=0\), \(d(q)=2\), \(d(r)=2\), \(d(s)=3\), and \(d(t)=4\).
The predecessor chain \(t,s,r,p\) reverses to the shortest route \(p,r,s,t\), of cost \(2+1+1=4\). As an independent check, the four possible routes to \(t\) have costs \(2+7=9\) through \(q\), \(2+4=6\) directly through \(r\), \(2+3+1=6\) through \(q,s\), and \(2+1+1=4\) through \(r,s\). The computed route has the least cost.
Common Pitfall: Processing by Label Instead of Order
A topological order is not an ordering by tentative distance. For example, take \(V=\{s,a,b,t\}\) and directed weighted edges \(s\to a:2\), \(s\to b:5\), \(b\to a:-10\), \(a\to t:1\), and \(b\to t:2\). The order \(s,b,a,t\) is topological. Processing \(s\) first gives labels \(d(a)=2\) and \(d(b)=5\). Processing \(b\) next improves \(d(a)\) to \(5+(-10)=-5\), and gives \(t\) the candidate \(5+2=7\). Processing \(a\) then improves \(d(t)\) to \(-5+1=-4\). The shortest route is \(s,b,a,t\), with cost \(5+(-10)+1=-4\).
If instead one processes \(a\) first because its tentative label \(2\) is smaller than \(b\)'s \(5\), one obtains the tentative route \(s,a,t\) of cost \(2+1=3\). Treating that label as final misses the later improvement through the negative edge \(b\to a\). The correction is to follow the topological order, not to choose the currently smallest label. Negative weights are allowed in a DAG, but they are precisely why distance labels need not increase as vertices are processed.
Using the Method Reliably
For each application, check the direction of every edge against the proposed order. Initialize all labels before relaxing any edge; skip a relaxation from a vertex whose label is \(\infty\). Record a predecessor only when a candidate decreases a label, and reconstruct a route only after all vertices have been processed. The proof explains why processing each outgoing edge once suffices: every possible last edge into a vertex comes from an earlier vertex in the order.
A DAG has no directed cycles, so it cannot contain a negative directed cycle. This is why negative edge weights do not prevent a shortest path from existing when a route exists. The method handles any real edge weights, including zero and positive weights, and works component by component even when some vertices cannot be reached from the chosen source.
Check Your Understanding
For each question, state the source and give the vertex order or route information needed to justify your answer.
- In the first worked example, what would \(d(c)\) be if the edge \(b\to a\) had weight \(2\) instead of \(-1\)? Trace the affected relaxations.
- Explain why every incoming edge of a vertex is relaxed before that vertex is processed in a topological order.
- For the second example, why does \(d(z)\) remain \(\infty\), even though all vertices are processed?
- In the third example, calculate the cost of each route to \(t\) and identify which predecessor pointer is used to reconstruct the minimum-cost route.
- Give a reason that a shortest path exists whenever a vertex is reachable from the source in a finite DAG with real edge weights.