An Immediate Algorithm for DAGs
Explore how to compute shortest paths in directed acyclic graphs by applying topological sorting and edge relaxation. This lesson explains the algorithm's correctness and analyzes its running time, helping you understand efficient methods for solving shortest path problems in weighted DAGs.
We'll cover the following...
Looking at the idea of path-relaxation, our first fleeting thought is a wish to magically conjure an ordering of the edges so that relaxing them in that order would compute the shortest paths for all vertices in a digraph.
It’s unlikely to discover such an algorithm for ordering of edges of an arbitrary directed graph, but for a certain class of directed graphs, such as the directed acyclic graphs (DAGs), the idea ties up neatly with the idea of topological sorting we discussed earlier.
When a DAG is topologically sorted, the vertices are ordered so that all edges in any path go from an earlier vertex in that ordered list to a later vertex in the list. This is also true for the edges of every shortest path. So just relaxing the outgoing edges from vertices—encountered in a topological sorted order—yields the correctly computed shortest paths. The correctness of this idea is a direct consequence of the path-relaxation principle.
Finding shortest paths in a DAG
We define the function ShortestPathsInDAG(G, s, weight) for finding the
shortest paths in the DAG ...