Bellman-Ford
Also known as: Bellman Ford algorithm
| Bellman-Ford computes single-source shortest paths even when some edge weights are negative (no negative cycle reachable from the source). It relaxes every edge $ | V | -1$ times; an extra pass that still improves a distance detects a negative cycle. |
Time $O(VE)$. Slower than Dijkstra on nonnegative instances, but the right tool when negatives appear or you need a negative-cycle check.
The recurrence “best path with at most $k$ edges” is a simple dynamic programming view of the same algorithm.