Single-source shortest-path problem
= Single-source shortest-path problem
{title2=$d_s(v)=d(s,v)$}
Compute <shortest-path distances> from one fixed source to every vertex, together with predecessor information when shortest paths exist. <Dijkstra's algorithm> handles nonnegative weights; the <Bellman-Ford algorithm> admits negative weights and detects reachable <negative cycles>. A <Directed acyclic graph> instead permits one pass in <topological order>.