What is the time complexity of bellman-ford?

Best case O(E) with early exit. Worst case O(V·E). Space complexity is O(V). V−1 relaxation passes, plus one more as a proof of no negative cycle.

Bellman-Ford

medium

After k passes, every shortest path using at most k edges is correct. A simple path uses at most V−1 edges - so if anything still improves on pass V, there is a negative cycle.

Best O(E) with early exitWorst O(V·E)Space O(V)

Loading the bellman-ford engine…

Where to go next

Dijkstra's algorithm

medium

Settle the closest unvisited node, then relax its edges.

Floyd-Warshall

medium

All pairs, three nested loops, one line of logic.

Topological sort

medium

Kahn's algorithm, with cycle detection for free.