 Single-source shortest-path problem

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.