Single-source shortest paths in directed acyclic graphs (DAG)

Single-source shortest paths in directed acyclic graphs (DAG)

Shortest paths are always well defined in a DAG, since even if there are negative-weight edges, no negative-weight cycles can exist.

The algorithm starts by topologically sorting the dag (see Topological sorting topic in blog) to impose a linear ordering on the vertices. If the dag contains a path from vertex u to vertex v, then u precedes v in the topological sort. We make just one pass over the vertices in the topologically sorted order.

As we process each vertex, we relax each edge that leaves the vertex.

The following theorem shows that the DAG-SHORTEST-PATHS procedure correctly computes the shortest paths.

The execution of the algorithm for shortest paths in a directed acyclic graph:

The vertices are topologically sorted from left to right. The source vertex is s. The d values appear within the vertices, and shaded edges indicate the  values.