3.4 Shortest paths in acyclic graphs¶
Part 2 · Trees and paths · Chapter 3 · Chapter 3: Shortest paths · Lecture notes, volume 2 (PDF) · Exercises: Shortest paths · App: Shortest paths: Dijkstra, Bellman–Ford, acyclic graphs
Definition 3.13: acyclic graph and topological order
A directed graph without directed cycles is a directed acyclic graph (DAG). A topological order of \(G=(N,A)\) is an ordering \(v_1,v_2,\dots,v_n\) of its nodes such that every arc goes forward:
Proposition 3.14: topological orders
A directed graph has a topological order if and only if it is acyclic.
Proof
If \(G\) has a topological order, a cycle \(i_0,i_1,\dots,i_k=i_0\) would go forward on every arc and come back to its first node: impossible. Conversely, let \(G\) be acyclic; we argue by induction on \(n\).
-
\(G\) has a node with no entering arc: otherwise, walking backwards along entering arcs from any node, after \(n\) steps a node repeats, and the walk contains a cycle.
-
Put such a node \(v_1\) first. The graph without \(v_1\) is acyclic, and by induction it has a topological order \(v_2,\dots,v_n\); no arc enters \(v_1\), so \(v_1,v_2,\dots,v_n\) is a topological order of \(G\). □
Algorithm: Shortest paths in an acyclic graph
STOP.Theorem 3.15: correctness and running time on acyclic graphs
On an acyclic graph with lengths of any sign, the algorithm «Shortest paths in an acyclic graph» ends with \(d(j)=\tilde{d}(j)\) for every \(j \in N\), and it runs in \(O(n+m)\) time.
Proof
An acyclic graph has no cycle at all, so (A2) holds. Every finite label is the length of a walk from \(s\), so \(d(j) \ge \tilde{d}(j)\) by Lemma 3.3; labels only decrease.
-
Let \(j\) be reachable and \(s=i_0,i_1,\dots,i_k=j\) a shortest path; its nodes appear in this order in the topological order, since every arc goes forward.
-
By induction on \(t\), after \(i_t\) is processed \(d(i_t) \le \tilde{d}(i_t)\): the path to \(i_{t-1}\) is shortest (Lemma 3.4), and processing \(i_{t-1}\) gives \(d(i_t) \le \tilde{d}(i_{t-1})+d_{i_{t-1}i_t}=\tilde{d}(i_t)\).
-
Nodes not reachable from \(s\) keep \(d(j)=+\infty=\tilde{d}(j)\).
Time. The topological order takes \(O(n+m)\) time with a counter of the entering arcs of every node, decreased when a tail is removed; Step 1 scans every arc once. □
-
The smallest-index rule fixes one order for the examples; any node without entering arcs can be removed.
-
With the lengths \(-d_{ij}\) the algorithm computes longest paths, since an acyclic graph has no cycle to repeat. Longest paths in acyclic graphs are the core of Chapter 9 «Project management».
Example 3.6: an acyclic instance
Reversing the arc \((4,3)\) of the reference graph into \((3,4)\), with \(d_{34}=1\), gives an acyclic graph. We give it the lengths of Example 3.1 except \(d_{54}=-3\) (red).
Step 0 gives the topological order \(1,3,2,5,4,6\): after \(1\), only \(3\) has no entering arc; then \(2\) and \(5\) are free, and \(2\) goes first. Each row of the table processes one node and shows the labels after it:
| step | node \(i\) | \(d(1)\) | \(d(2)\) | \(d(3)\) | \(d(4)\) | \(d(5)\) | \(d(6)\) |
|---|---|---|---|---|---|---|---|
| \(1\) | \(1\) | \(0\) | \(7\) | \(2\) | \(\infty\) | \(\infty\) | \(\infty\) |
| \(2\) | \(3\) | \(0\) | \(5\) | \(2\) | \(3\) | \(10\) | \(\infty\) |
| \(3\) | \(2\) | \(0\) | \(5\) | \(2\) | \(3\) | \(10\) | \(\infty\) |
| \(4\) | \(5\) | \(0\) | \(5\) | \(2\) | \(3\) | \(10\) | \(17\) |
| \(5\) | \(4\) | \(0\) | \(5\) | \(2\) | \(3\) | \(10\) | \(8\) |
| \(6\) | \(6\) | \(0\) | \(5\) | \(2\) | \(3\) | \(10\) | \(8\) |
The predecessors give the tree \((1,3)\), \((3,2)\), \((3,4)\), \((3,5)\), \((4,6)\) (blue). The negative arc \((5,4)\) is not used: \(d(5)-3=7>3=d(4)\). With the lengths \(-d_{ij}\) the longest path lengths from \(1\) are \((0,7,2,10,10,17)\).
A graph is acyclic if and only if it has a topological order. Scanning the nodes in that order, each label is final when its node is processed: shortest paths in \(O(n+m)\) time, with lengths of any sign.