Shortest distances from 1 on a directed acyclic graph. Sort the vertices topologically, 0, 1, 2, 3, 4, 5, so that every edge points forward. Then walk that order once, relaxing each vertex's outgoing edges: by the time a vertex is reached, every path into it has already been counted, so its distance is final without any heap and even with negative weights.
DAG shortest path from 1 in topological order 0, 1, 2, 3, 4, 5.
Next in order: 0, still at infinity. Nothing reaches it from 1, so its edges are skipped.
0 is unreachable, skipped.
Next in order: 1 at 0. Every edge into 1 came from a vertex earlier in the order, so 0 is final. Relax its 2 outgoing edges.
1 is final at 0.
Relax 1 to 2: 0 + 2 = 2 against 2's current infinity. Shorter, so 2 becomes 2 with 1 as its parent.
Edge 1 to 2: 2 against infinity. Improved.
Relax 1 to 3: 0 + 6 = 6 against 3's current infinity. Shorter, so 3 becomes 6 with 1 as its parent.
Edge 1 to 3: 6 against infinity. Improved.
Next in order: 2 at 2. Every edge into 2 came from a vertex earlier in the order, so 2 is final. Relax its 3 outgoing edges.
2 is final at 2.
Relax 2 to 3: 2 + 7 = 9 against 3's current 6. Not shorter, so 3 keeps 6.
Edge 2 to 3: 9 against 6. No change.
Relax 2 to 4: 2 + 4 = 6 against 4's current infinity. Shorter, so 4 becomes 6 with 2 as its parent.
Edge 2 to 4: 6 against infinity. Improved.
Relax 2 to 5: 2 + 2 = 4 against 5's current infinity. Shorter, so 5 becomes 4 with 2 as its parent.
Edge 2 to 5: 4 against infinity. Improved.
Next in order: 3 at 6. Every edge into 3 came from a vertex earlier in the order, so 6 is final. Relax its 1 outgoing edge.
3 is final at 6.
Relax 3 to 4: 6 + -1 = 5 against 4's current 6. Shorter, so 4 becomes 5 with 3 as its parent.
Edge 3 to 4: 5 against 6. Improved.
Next in order: 4 at 5. Every edge into 4 came from a vertex earlier in the order, so 5 is final. Relax its 1 outgoing edge.
4 is final at 5.
Relax 4 to 5: 5 + -2 = 3 against 5's current 4. Shorter, so 5 becomes 3 with 4 as its parent.
Edge 4 to 5: 3 against 4. Improved.
Next in order: 5 at 3. Every edge into 5 came from a vertex earlier in the order, so 3 is final. It has no outgoing edges.
5 is final at 3.
Distances from 1: 0: infinity, 1: 0, 2: 2, 3: 6, 4: 5, 5: 3. One pass over the order, 7 relaxations, O(V + E) after the topological sort, and negative weights are fine because no vertex is ever revisited. Unreachable: 0.
DAG shortest paths finished. vertex 0 at infinity, vertex 1 at 0, vertex 2 at 2, vertex 3 at 6, vertex 4 at 5, vertex 5 at 3.