Graph Theory37 sections · 1633 units
Open in Course

Why $n-1$ Iterations

(Maximum path length)

In a graph with nn nodes, the longest simple path (no repeated nodes) has n1n-1 edges. You cannot have a simple path with nn or more edges without repeating a node, which creates a cycle. After round 11, you have shortest paths with 1\leq 1 edge. After round 22, shortest paths with 2\leq 2 edges.

After round kk, shortest paths with k\leq k edges. After n1n-1 rounds, you have checked all possible simple paths. If no negative cycle exists, distances stop changing because you have found the true shortest paths. If distances still change, a negative cycle exists.