An Immediate Algorithm for DAGs
Learn about a single-source shortest-paths algorithm for directed acyclic graphs.
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 ...