Graph Theory37 sections · 1633 units
Open in Course

Bellman-Ford Strategy

(Relax all edges repeatedly)

Bellman-Ford relaxes every edge in the graph, then repeats this process multiple times. Each complete pass through all edges is called one iteration or one round. After kk rounds, you have found shortest paths using at most kk edges. This is because each round extends shortest paths by one more edge.

Since the shortest path between any two nodes uses at most n1n-1 edges (no repeated nodes), running n1n-1 rounds guarantees correct distances for all nodes. If no negative cycle exists, distances stabilize after n1n-1 rounds.