What is the Bellman-Ford algorithm?

The Bellman-Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.

How does Bellman-Ford detect negative cycles?

After V-1 iterations (where V is the number of vertices), the algorithm performs one more iteration. If any shortest path distance is updated during this final iteration, it indicates the presence of a negative-weight cycle reachable from the source.

Graph Algorithms

Bellman-Ford Algorithm

The robust algorithm for finding single-source shortest paths, uniquely capable of handling negative edge weights and detecting negative cycles.

Bellman-Ford Implementation

This implementation finds the shortest paths from a source node to all other nodes by repeatedly relaxing edges.

                            function bellmanFord(vertices, edges, source) {
                            const distance = new Array(vertices).fill(Infinity);
                            distance[source] = 0;
                            
                            // Relax edges repeatedly
                            for (let i = 0; i < vertices - 1; i++) {
                            for (const [u, v, weight] of edges) {
                            if (distance[u] !== Infinity && distance[u] + weight < distance[v]) {
                            distance[v] = distance[u] + weight;
                            }
                            }
                            }
                            
                            // Check for negative-weight cycles
                            for (const [u, v, weight] of edges) {
                            if (distance[u] !== Infinity && distance[u] + weight < distance[v]) {
                            return 'Graph contains a negative-weight cycle';
                            }
                            }
                            
                            return distance;
                            }
                        

AI Coach Hint: While Dijkstra's is faster for graphs with non-negative weights, Bellman-Ford is your go-to for graphs with negative weights. Always be prepared to discuss the trade-offs and why you'd choose one over the other in an interview setting.