= Solution
<Dijkstra's algorithm> solves the <single-source shortest-path problem> with nonnegative edge weights: it finds minimum path lengths from the source to all reachable vertices and can store predecessor edges. With <adjacency lists> and a binary-heap <priority queue>, it takes \b[$O((|V|+|E|)\log|V|)$ time]; a direct array implementation takes $O(|V|^2)$.
The <Bellman-Ford algorithm> allows negative edge weights. If no negative-weight cycle is reachable from the source, it computes the finite shortest-path distances to reachable vertices and identifies unreachable ones. Otherwise it can report a reachable <negative cycle>, whose repeated traversal makes distances to some reachable vertices unbounded below. It performs at most $|V|-1$ full relaxation rounds and one further detection round, taking \b[$O(|V||E|+|V|)$ time], conventionally written $O(|V||E|)$ for nontrivial edge sets. A negative cycle unreachable from the source does not affect its distance problem.
Back to article page
