Bellman-Ford Algorithm Shortest Path in Graph with Negative Weights

Problem Statement❯

Given a weighted, directed, and connected graph with V vertices and E edges, the task is to find the shortest distance from a given source vertex S to all other vertices.

Note: If the graph contains a negative weight cycle that is reachable from the source, return an array containing only -1.

Examples❯

Vertices	Edges	Output	Description
5	[(0,1,5), (0,2,4), (1,3,3), (2,1,6), (3,2,-2)]	[0,5,4,8,INF]	Shortest paths from source 0 to all vertices
3	[(0,1,1), (1,2,-1), (2,0,-1)]	[-1]	Graph contains a negative weight cycle
4	[(0,1,1), (0,2,4), (1,2,-2), (2,3,2)]	[0,1,-1,1]	Graph with negative weights, but no cycle
2	[(0,1,3)]	[0,3]	Simple two-node graph
1	[]	[0]	Graph with only one node

Solution❯

The Bellman-Ford algorithm is used to compute the shortest paths from a single source vertex to all other vertices in a graph that may have negative weight edges. Unlike Dijkstra's algorithm, Bellman-Ford can handle graphs with negative weights and also detects negative weight cycles.

The idea is to relax all the edges V-1 times (where V is the number of vertices). Relaxing an edge means updating the distance to a vertex if a shorter path is found.

Start by setting the distance to the source node as 0 and all others as infinity.
Iteratively update the distances using each edge (u, v, w) such that if dist[u] + w < dist[v], then update dist[v].
After V-1 iterations, check once more: if any edge can still be relaxed, a negative weight cycle exists. Return [-1] in that case.

Bellman-Ford is slower than Dijkstra’s algorithm but more versatile in handling negative edges and cycles.

Algorithm Steps❯

Initialize a distance array dist[] of size V with all values as Infinity, except dist[S] = 0.
Repeat V-1 times:
1. For each edge (u, v, wt) in the graph:
2. If dist[u] + wt < dist[v], update dist[v] = dist[u] + wt.
For each edge (u, v, wt), check again:
1. If dist[u] + wt < dist[v], return [-1] (negative cycle detected).
Return dist[] as the final result.

Code

JavaScript

function bellmanFord(V, edges, S) {
  const dist = Array(V).fill(Infinity);
  dist[S] = 0;

  for (let i = 1; i < V; i++) {
    for (const [u, v, wt] of edges) {
      if (dist[u] !== Infinity && dist[u] + wt < dist[v]) {
        dist[v] = dist[u] + wt;
      }
    }
  }

  for (const [u, v, wt] of edges) {
    if (dist[u] !== Infinity && dist[u] + wt < dist[v]) {
      return [-1]; // Negative weight cycle detected
    }
  }

  return dist;
}

const edges1 = [[0,1,5],[0,2,4],[1,3,3],[2,1,6],[3,2,-2]];
console.log("Shortest paths:", bellmanFord(5, edges1, 0));

const edges2 = [[0,1,1],[1,2,-1],[2,0,-1]];
console.log("Cycle detection:", bellmanFord(3, edges2, 0));

⬅ Previous TopicMinimum Multiplications to Reach End - Graph BFS

Next Topic ⮕Floyd Warshall Algorithm for All-Pairs Shortest Path