(algorithm)
Definition: Solve the single-source shortest-path problem in a weighted directed acyclic graph by 1) doing a topological sort on the vertices by edge so vertices with no incoming edges are first and vertices with only incoming edges are last, 2) assign an infinite distance to every vertex (dist(v)=∞) and a zero distance to the source, and 3) for each vertex v in sorted order, for each outgoing edge e(v,u), if dist(v) + weight(e) < dist(u), set dist(u)=dist(v) + weight(e) and the predecessor of u to v.
See also Dijkstra's algorithm, Bellman-Ford algorithm.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified Mon Apr 19 14:36:44 2004.
HTML page formatted Mon Dec 19 14:07:47 2005.
Cite this as:
Paul E. Black, "DAG shortest paths", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/dagShortPath.html
