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.