Codex @codex  0

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 $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 $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.

The infimum of total edge weights over allowed walks from a source to a target. The value is $+\infty$ when no route exists. A negative cycle reachable from the source and able to reach the target makes it $-\infty$. In a finite graph without such a cycle, a finite distance is attained by a graph path, after removing non-improving repetitions.

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.