ProgramGuru

Bellman-Ford Algorithm for Shortest Paths

Problem and examples

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.

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

How it works

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.

  1. Initialize a distance array dist[] of size V with all values as Infinity, except dist[S] = 0.
  2. 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.
  3. For each edge (u, v, wt), check again:
    1. If dist[u] + wt < dist[v], return [-1] (negative cycle detected).
  4. Return dist[] as the final result.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <limits.h>

#define MAXV 100
#define MAXE 1000

void bellmanFord(int V, int E, int edges[][3], int S) {
    int dist[MAXV];
    for (int i = 0; i < V; i++) dist[i] = INT_MAX;
    dist[S] = 0;

    for (int i = 1; i < V; i++) {
        for (int j = 0; j < E; j++) {
            int u = edges[j][0];
            int v = edges[j][1];
            int wt = edges[j][2];
            if (dist[u] != INT_MAX && dist[u] + wt < dist[v]) {
                dist[v] = dist[u] + wt;
            }
        }
    }

    for (int j = 0; j < E; j++) {
        int u = edges[j][0];
        int v = edges[j][1];
        int wt = edges[j][2];
        if (dist[u] != INT_MAX && dist[u] + wt < dist[v]) {
            printf("-1\n");
            return;
        }
    }

    for (int i = 0; i < V; i++) {
        printf("%d ", dist[i]);
    }
    printf("\n");
}

int main() {
    int edges1[5][3] = {{0,1,5},{0,2,4},{1,3,3},{2,1,6},{3,2,-2}};
    printf("Shortest paths:\n");
    bellmanFord(5, 5, edges1, 0);

    int edges2[3][3] = {{0,1,1},{1,2,-1},{2,0,-1}};
    printf("Cycle detection:\n");
    bellmanFord(3, 3, edges2, 0);
    return 0;
}

C++ implementation

#include <iostream>
#include <vector>
using namespace std;

vector<int> bellmanFord(int V, vector<vector<int>>& edges, int S) {
    vector<int> dist(V, INT_MAX);
    dist[S] = 0;

    for (int i = 1; i < V; ++i) {
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], wt = edge[2];
            if (dist[u] != INT_MAX && dist[u] + wt < dist[v]) {
                dist[v] = dist[u] + wt;
            }
        }
    }

    for (auto& edge : edges) {
        int u = edge[0], v = edge[1], wt = edge[2];
        if (dist[u] != INT_MAX && dist[u] + wt < dist[v]) {
            return {-1};
        }
    }

    return dist;
}

int main() {
    vector<vector<int>> edges1 = {{0,1,5},{0,2,4},{1,3,3},{2,1,6},{3,2,-2}};
    vector<int> result1 = bellmanFord(5, edges1, 0);
    cout << "Shortest paths:\n";
    for (int d : result1) cout << d << " ";
    cout << endl;

    vector<vector<int>> edges2 = {{0,1,1},{1,2,-1},{2,0,-1}};
    vector<int> result2 = bellmanFord(3, edges2, 0);
    cout << "Cycle detection:\n";
    for (int d : result2) cout << d << " ";
    cout << endl;
    return 0;
}

Python implementation

def bellman_ford(V, edges, S):
    dist = [float('inf')] * V
    dist[S] = 0

    for _ in range(V - 1):
        for u, v, wt in edges:
            if dist[u] != float('inf') and dist[u] + wt < dist[v]:
                dist[v] = dist[u] + wt

    for u, v, wt in edges:
        if dist[u] != float('inf') and dist[u] + wt < dist[v]:
            return [-1]

    return dist

print("Shortest paths:", bellman_ford(5, [[0,1,5],[0,2,4],[1,3,3],[2,1,6],[3,2,-2]], 0))
print("Cycle detection:", bellman_ford(3, [[0,1,1],[1,2,-1],[2,0,-1]], 0))

Java implementation

import java.util.*;

public class BellmanFord {
    public static int[] bellmanFord(int V, int[][] edges, int S) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[S] = 0;

        for (int i = 1; i < V; i++) {
            for (int[] edge : edges) {
                int u = edge[0], v = edge[1], wt = edge[2];
                if (dist[u] != Integer.MAX_VALUE && dist[u] + wt < dist[v]) {
                    dist[v] = dist[u] + wt;
                }
            }
        }

        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], wt = edge[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + wt < dist[v]) {
                return new int[]{-1};
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int[][] edges1 = {{0,1,5},{0,2,4},{1,3,3},{2,1,6},{3,2,-2}};
        System.out.println("Shortest paths:");
        System.out.println(Arrays.toString(bellmanFord(5, edges1, 0)));

        int[][] edges2 = {{0,1,1},{1,2,-1},{2,0,-1}};
        System.out.println("Cycle detection:");
        System.out.println(Arrays.toString(bellmanFord(3, edges2, 0)));
    }
}

JavaScript implementation

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];
    }
  }

  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));

Go implementation

package main

import (
	"fmt"
	"math"
)

func bellmanFord(V int, edges [][3]int, S int) []int {
	dist := make([]int, V)
	for i := range dist {
		dist[i] = math.MaxInt32
	}
	dist[S] = 0

	for i := 1; i < V; i++ {
		for _, edge := range edges {
			u, v, wt := edge[0], edge[1], edge[2]
			if dist[u] != math.MaxInt32 && dist[u]+wt < dist[v] {
				dist[v] = dist[u] + wt
			}
		}
	}

	for _, edge := range edges {
		u, v, wt := edge[0], edge[1], edge[2]
		if dist[u] != math.MaxInt32 && dist[u]+wt < dist[v] {
			return []int{-1}
		}
	}
	return dist
}

func main() {
	edges1 := [][3]int{{0, 1, 5}, {0, 2, 4}, {1, 3, 3}, {2, 1, 6}, {3, 2, -2}}
	fmt.Println("Shortest paths:", bellmanFord(5, edges1, 0))

	edges2 := [][3]int{{0, 1, 1}, {1, 2, -1}, {2, 0, -1}}
	fmt.Println("Cycle detection:", bellmanFord(3, edges2, 0))
}

Rust implementation

fn bellman_ford(v: usize, edges: &Vec<(usize, usize, i32)>, s: usize) -> Vec<i32> {
    let mut dist = vec![i32::MAX; v];
    dist[s] = 0;

    for _ in 0..v - 1 {
        for &(u, vtx, wt) in edges.iter() {
            if dist[u] != i32::MAX && dist[u] + wt < dist[vtx] {
                dist[vtx] = dist[u] + wt;
            }
        }
    }

    for &(u, vtx, wt) in edges.iter() {
        if dist[u] != i32::MAX && dist[u] + wt < dist[vtx] {
            return vec![-1];
        }
    }
    dist
}

fn main() {
    let edges1 = vec![(0,1,5),(0,2,4),(1,3,3),(2,1,6),(3,2,-2)];
    println!("Shortest paths: {:?}", bellman_ford(5, &edges1, 0));
    let edges2 = vec![(0,1,1),(1,2,-1),(2,0,-1)];
    println!("Cycle detection: {:?}", bellman_ford(3, &edges2, 0));
}

Kotlin implementation

fun bellmanFord(V: Int, edges: Array<IntArray>, S: Int): IntArray {
    val dist = IntArray(V) { Int.MAX_VALUE }
    dist[S] = 0

    for (i in 1 until V) {
        for (edge in edges) {
            val (u, v, wt) = edge
            if (dist[u] != Int.MAX_VALUE && dist[u] + wt < dist[v]) {
                dist[v] = dist[u] + wt
            }
        }
    }

    for (edge in edges) {
        val (u, v, wt) = edge
        if (dist[u] != Int.MAX_VALUE && dist[u] + wt < dist[v]) {
            return intArrayOf(-1)
        }
    }
    return dist
}

fun main() {
    val edges1 = arrayOf(intArrayOf(0,1,5), intArrayOf(0,2,4), intArrayOf(1,3,3), intArrayOf(2,1,6), intArrayOf(3,2,-2))
    println("Shortest paths: " + bellmanFord(5, edges1, 0).joinToString())

    val edges2 = arrayOf(intArrayOf(0,1,1), intArrayOf(1,2,-1), intArrayOf(2,0,-1))
    println("Cycle detection: " + bellmanFord(3, edges2, 0).joinToString())
}

Swift implementation

func bellmanFord(V: Int, edges: [(Int, Int, Int)], S: Int) -> [Int] {
    var dist = [Int](repeating: Int.max, count: V)
    dist[S] = 0

    for _ in 1..<V {
        for (u, v, wt) in edges {
            if dist[u] != Int.max && dist[u] + wt < dist[v] {
                dist[v] = dist[u] + wt
            }
        }
    }

    for (u, v, wt) in edges {
        if dist[u] != Int.max && dist[u] + wt < dist[v] {
            return [-1]
        }
    }
    return dist
}

let edges1 = [(0,1,5),(0,2,4),(1,3,3),(2,1,6),(3,2,-2)]
print("Shortest paths:", bellmanFord(V: 5, edges: edges1, S: 0))

let edges2 = [(0,1,1),(1,2,-1),(2,0,-1)]
print("Cycle detection:", bellmanFord(V: 3, edges: edges2, S: 0))

TypeScript implementation

function bellmanFord(V: number, edges: [number, number, number][], S: number): number[] {
  const dist: number[] = new 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];
    }
  }

  return dist;
}

const edges1: [number, number, number][] = [[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: [number, number, number][] = [[0,1,1],[1,2,-1],[2,0,-1]];
console.log("Cycle detection:", bellmanFord(3, edges2, 0));