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❯

Understanding the Problem

The Bellman-Ford Algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted graph. Unlike Dijkstra's algorithm, Bellman-Ford supports negative weight edges and is capable of detecting negative weight cycles — cycles where the total sum of edge weights is negative.

This algorithm is especially useful in scenarios like financial networks or graphs with penalties, where such negative weights naturally occur.

Step-by-Step Solution with Example

Step 1: Initialize the Distance Array

Assume a graph with 5 vertices (numbered 0 to 4) and the following edges:


edges = [
  [0, 1, 6],
  [0, 2, 7],
  [1, 2, 8],
  [1, 3, 5],
  [1, 4, -4],
  [2, 3, -3],
  [2, 4, 9],
  [3, 1, -2],
  [4, 3, 7]
]
source = 0

We initialize a dist[] array such that dist[source] = 0 and all others as Infinity.

Step 2: Relax All Edges V-1 Times

We iterate over all edges V - 1 times (where V is the number of vertices). During each pass, we attempt to "relax" each edge:

If dist[u] + weight < dist[v], update dist[v] = dist[u] + weight.

After each pass, the algorithm slowly propagates the shortest path information throughout the graph.

Step 3: Detect Negative Weight Cycle

After performing V-1 iterations, we perform one extra pass over all edges. If any distance can still be reduced, it means a negative weight cycle exists in the graph.

In that case, the algorithm should return [-1] to indicate the presence of such a cycle.

Step 4: Final Result

If no negative cycles are detected, return the dist[] array, which contains the shortest distances from the source to every other vertex.


[0, 2, 7, 4, -2]   // For the given example

Edge Cases

Graph with no edges: All nodes remain at Infinity distance except the source.
Negative edge but no cycle: Bellman-Ford handles it correctly.
Disconnected graph: Vertices that are not reachable from the source remain at Infinity.
Negative weight cycle: If a cycle exists that can endlessly decrease the path cost, the algorithm detects it and should return [-1].

Finally

The Bellman-Ford algorithm is an essential tool when dealing with graphs that include negative edge weights. While it's not as fast as Dijkstra’s algorithm for graphs with only positive weights, its ability to detect negative cycles makes it extremely valuable.

By following a clear step-by-step relaxation process and checking for further improvements in the last iteration, we ensure both correctness and cycle detection. Understanding this approach builds a strong foundation for handling more complex graph problems.

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

Comments

Loading comments...