Skip to content

DAG Shortest Path

Summarized notes on Introduction to Algorithms, Chapter 24

  • If DAG contains path from \(u\) to \(v\) then \(u\) precedes \(v\) in topological sort
  • Make just one pass over vertices and relax edges that leave the vertex
  • critical path is the longest path through the DAG
    → to find critical path, negate edge weights then run DAG-Shortest-Paths

Pseudo code implementation

1
2
3
4
5
6
Dag-shortest-paths(G, w, s)
    topologically sort vertices of G
    Initialize-single-source(G, s)
    for each vertex u, taken in topologically sorted order
        for each vertex v in G.Adj[u]
            Relax(u, v, w)

Complexity

Running Time
\(\Theta(V+E)\) DAG-shortest-path