Bellman-Ford Algorithm

Graph Theory · Axiom Academy

Finding shortest paths with negative edge weights and detecting negative cycles The fundamental operation in Bellman-Ford is edge relaxation . For each edge (u, v) with weight w, we check if going through u provides a shorter path to v than the current known distance. If dist[u] + w(u,v) < dist[v], we update dist[v] to this shorter distance. This process is called "relaxing" the edge. The algorithm performs exactly V-1 iterations (where V is the number of vertices), relaxing all edges in each iteration. This is sufficient because: The longest simple path in a graph has at most V-1 edges. After k iterations, the algorithm has found all shortest paths with at most k edges. Therefore, after V-1 iterations, all shortest paths are guaranteed to be found. After V-1 iterations, if we can still relax any edge, a negative cycle must exist. This is because shortest paths should be finalized after V-1 iterations in graphs without negative cycles. A negative cycle makes the shortest path problem ill-defined, as we can keep traversing the cycle to get arbitrarily small path costs. 4. Comparison with Dijkstra's Algorithm Bellman-Ford and Dijkstra's algorithm both solve the single-source shortest path problem, but they have different capabilities and performance characteristics: The Bellman-Ford algorithm has a time complexity of O(VE) , where V is the number of vertices and E is the number of edges. Inner operation: Relax all E edges Space complexity: O(V) for distance array

This is the written version of the interactive lesson above. See the full Graph Theory course.