Bellman-Ford Algorithm: Finding shortest path from a node

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

Algorithm
Complexity
Pseudocode
Implementations
Applications
Discussions

Reading time: 15 minutes | Coding time: 9 minutes

Bellman-Ford Algorithm is an algorithm for single source shortest path where edges can be negative (but if there is a cycle with negative weight, then this problem will be NP).

The credit of Bellman-Ford Algorithm goes to Alfonso Shimbel, Richard Bellman, Lester Ford and Edward F. Moore.

In loving memory of Richard Ernest Bellman

The main idea is to relax all the edges exactly n - 1 times (read relaxation above in dijkstra). You can prove this algorithm using induction.
If in the n - th step, we relax an edge, then we have a negative cycle (this is if and only if).

The steps involved are:

The outer loop traverses from 0 to N
Loop over all edges, check if the next node distance > current node distance + edge weight, in this case update the next node distance to "current node distance + edge weight".

This algorithm depends on the relaxation principle where the shortest distance for all vertices is gradually replaced by more accurate values until eventually reaching the optimum solution. In the beginning all vertices have a distance of "Infinity", but only the distance of the source vertex = 0, then update all the connected vertices with the new distances (source vertex distance + edge weights), then apply the same concept for the new vertices with new distances and so on.

Pseudocode


Bellman-Ford(int v)
	d[i] = inf for each vertex i
	d[v] = 0
	for step = 1 to n
		for all edges like e
			i = e.first // first end
			j = e.second // second end
			w = e.weight
			if d[j] > d[i] + w
				if step == n
					then return "Negative cycle found"
				d[j] = d[i] + w

Complexity

Worst case time complexity: Θ(VE)
Average case time complexity: Θ(VE)
Best case time complexity: Θ(E)
Space complexity: Θ(V)

Implementations

C
C++
Java
Python

C


#include <stdio.h>
void relax(int u, int v, double w, double d[], int pi[]) {
  if (d[v] > d[u] + w) {
    d[v] = d[u] + w;
    pi[v] = u;
  }
}
void initialize_single_source(double d[], int pi[], int s, int n) {
  int i;
  for (i = 1; i<= n; ++i) {
    d[i] = 1000000000.0;
    pi[i] = 0;
  }
  d[s] = 0.0;
}
int bellman_ford(int first[], int node[], int next[], double w[], double d[],
  int pi[], int s, int n) {
  int u, v, i, j;
  initialize_single_source(d, pi, s, n);
  for (i = 1; i<= n-1; ++i) {
    for (u = 1; u <= n; ++u) {
      j = first[u];
      while (j > 0) {
       v = node[j];
       relax(u, v, w[j], d, pi);
       j = next[j];
     }
   }
 }
 for (u = 1; u <= n; ++u) {
  j = first[u];
  while (j > 0) {
    v = node[j];
    if (d[v] > d[u] + w[j])
     return 0;
   j = next[j];
 }
}
return 1;
}
int main(void) {
  int first[6], node[11], next[11], pi[6];
  double w[11], d[6];
  int s;
  int i;
  int ok;
  first[1] = 1;
  first[2] = 3;
  first[3] = 6;
  first[4] = 7;
  first[5] = 9;
  node[1] = 2;
  node[2] = 4;
  node[3] = 3;
  node[4] = 4;
  node[5] = 5;
  node[6] = 2;
  node[7] = 3;
  node[8] = 5;
  node[9] = 1;
  node[10] = 3;
  w[1] = 6.0;
  w[2] = 7.0;
  w[3] = 5.0;
  w[4] = 8.0;
  w[5] = -4.0;
  w[6] = -2.0;
  w[7] = -3.0;
  w[8] = 9.0;
  w[9] = 2.0;
  w[10] = 7.0;
  next[1] = 2;
  next[2] = 0;
  next[3] = 4;
  next[4] = 5;
  next[5] = 0;
  next[6] = 0;
  next[7] = 8;
  next[8] = 0;
  next[9] = 10;
  next[10] = 0;
  printf("Enter source node: ");
  scanf("%d", &s);
  ok = bellman_ford(first, node, next, w, d, pi, s, 5);
  printf("bellman_ford returns ");
  printf("%d\n\n", ok);
  for (i = 1; i<= 5; ++i) {
    printf("%d: %f  %d\n", i, d[i], pi[i]);
  }
  return 0;
}

C++


#include <iostream>
#include <map>
#include <vector>
#include <utility>
#include <unordered_map>
#include <algorithm>
#include <string>
#include <climits>
int nodes,edges;
// Path of Cosmos by OpenGenus Foundation
void path_finding(int source, std::unordered_map<int,int> parent_map)
{
	using namespace std;
	string str;
	while(parent_map[source]!=source)
	{
		str.append(to_string(source));
		str.append(" ");
		source=parent_map[source];
	}
	str.append(to_string(source));
	reverse(str.begin(),str.end());
	cout<<"Path\n";
	cout<<str<<endl;
}
void print_distance(std::vector<int> distance)
{
	using namespace std;
	cout << "Distance of vertex corresponding from source\n";
	for(size_t i=0; i < distance.size(); ++i)
	{
		cout << i << "\t\t" << distance[i] << endl;
	}
}
void BellmanFord(std::vector<std::pair<int, std::pair<int,int>> > graph, int source, std::unordered_map<int,int> &parent_map)
{
	using namespace std;
	vector<int> distance(nodes, INT_MAX);
	distance[source]=0;
// Relax all edges nodes-1 times to get the shortest possible distance
	for(int i=0;i<nodes;i++)
	{
		for(int j=0;j<edges;j++)
		{
			int source=graph[j].second.first;
			int destination=graph[j].second.second;
			int weight=graph[j].first;
			if(distance[source]!=INT_MAX&&distance[source]+weight<distance[destination])
			{
				distance[destination]=distance[source]+weight;
				parent_map[destination]=source;
			}
		}
	}
/* If after relaxing all edges for nodes-1 time we still get a shorter path that indicates
 a negative weight cycle */
	for(int j=0;j<edges;j++)
		{
			int source=graph[j].second.first;
			int destination=graph[j].second.second;
			int weight=graph[j].first;
			if(distance[source]!=INT_MAX&&distance[source]+weight<distance[destination])
			{
				cout<<"Graph contains negative weight cycle\n";
				exit(0);
			}
		}
	print_distance(distance);
}
int main()
{
	using namespace std;
	vector<pair<int,pair<int,int>> > graph;
	unordered_map<int,int> parent_map;
	int source,init_path;
	cout<<"Enter number of nodes in graph\n";
	cin>>nodes;
	cout<<"Enter number of edges is graph\n";
	cin>>edges;
	for(int i=0;i<edges;i++)
	{
		int src,dest,weight;
		cout<<"Enter source vertex(zero indexed)\n";
		cin>>src;
		cout<<"Enter destination vertex(zero indexed)\n";
		cin>>dest;
		cout<<"Enter weight of edge\n";
		cin>>weight;
		graph.push_back(make_pair(weight,make_pair(src,dest)));
	}
	cout<<"Enter initial vertex(zero indexed)\n";
	cin>>source;
	BellmanFord(graph,source,parent_map);
	cout<<"Enter destination vertex for path finding(zero indexed)\n";
	cin>>init_path;
	path_finding(init_path,parent_map);
	return 0;
}

Java


/**
 * An implementation of the Bellman-Ford algorithm. The algorithm finds
 * the shortest path between a starting node and all other nodes in the graph. 
 * The algorithm also detects negative cycles.
 *
 * @author William Fiset, william.alexandre.fiset@gmail.com
 **/
public class BellmanFordEdgeList {
  // A directed edge
  public static class Edge {
    double cost;
    int from, to;
    public Edge(int from, int to, double cost) {
      this.to = to;
      this.from = from;
      this.cost = cost;
    }
  }
  /**
   * An implementation of the Bellman-Ford algorithm. The algorithm finds
   * the shortest path between a starting node and all other nodes in the graph. 
   * The algorithm also detects negative cycles. If a node is part of a negative 
   * cycle then the minimum cost for that node is set to Double.NEGATIVE_INFINITY.
   *
   * @param edges - An edge list containing directed edges forming the graph
   * @param V     - The number of vertices in the graph.
   * @param start - The id of the starting node
   **/
  public static double[] bellmanFord(Edge[] edges, int V, int start) {
    double[] dist = new double[V];
    java.util.Arrays.fill(dist, Double.POSITIVE_INFINITY);
    dist[start] = 0;
    // For each vertex, apply relaxation for all the edges
    for (int v = 0; v < V-1; v++)
      for (Edge edge : edges)
        if (dist[edge.from] + edge.cost < dist[edge.to])
          dist[edge.to] = dist[edge.from] + edge.cost;
    // Run algorithm a second time to detect which nodes are part
    // of a negative cycle. A negative cycle has occurred if we 
    // can find a better path beyond the optimal solution.
    for (int v = 0; v < V-1; v++)
      for (Edge edge : edges)
        if (dist[edge.from] + edge.cost < dist[edge.to])
          dist[edge.to] = Double.NEGATIVE_INFINITY;
    // Return the array containing the shortest distance to every node
    return dist;
  }
  public static void main(String[] args) { 
    int E = 10, V = 9, start = 0;
    Edge [] edges = new Edge[E];
    edges[0] = new Edge(0,1,1);
    edges[1] = new Edge(1,2,1);
    edges[2] = new Edge(2,4,1);
    edges[3] = new Edge(4,3,-3);
    edges[4] = new Edge(3,2,1);
    edges[5] = new Edge(1,5,4);
    edges[6] = new Edge(1,6,4);
    edges[7] = new Edge(5,6,5);
    edges[8] = new Edge(6,7,4);
    edges[9] = new Edge(5,7,3);
    double[] d = bellmanFord(edges, V, start);
    for (int i = 0; i < V; i++)
      System.out.printf("The cost to get from node %d to %d is %.2f\n", start, i, d[i] );
    // Output:
    // The cost to get from node 0 to 0 is 0.00
    // The cost to get from node 0 to 1 is 1.00
    // The cost to get from node 0 to 2 is -Infinity
    // The cost to get from node 0 to 3 is -Infinity
    // The cost to get from node 0 to 4 is -Infinity
    // The cost to get from node 0 to 5 is 5.00
    // The cost to get from node 0 to 6 is 5.00
    // The cost to get from node 0 to 7 is 8.00
    // The cost to get from node 0 to 8 is Infinity
  }
}

Python


# part of cosmos by OpenGenus Foundation
from collections import defaultdict
# Part of Cosmos by OpenGenus Foundation
class Graph:
	def __init__(self,vertices):
		self.V = vertices # # of vertices
		self.graph = []
	# add edge to graph
	def addEdge(self, u,v,w):
		self.graph.append([u,v,w])
	# print solution
	def printArr(self,dist):
		print("Vertex Distance from Source ")
		for i in range(self.V):
			print("%d -> %d" % (i,dist[i]))
	# main function for bellman ford algo. Also detects negative weight cycles
	def bellmanFord(self,src):
		# init all distances from source to all as INFINITE
		dist = [float("Inf")] * self.V
		dist[src] = 0
		# relax all edges |V|-1 times.
		for i in range(self.V - 1):
			# update dist value and parent index of adjacent values of picked vertex.
			# consider those which are still in queue.
			for u, v, w in self.graph:
				if dist[u] != float("Inf") and dist[u] + w < dist[v]:
					dist[v] = dist[u] + w
		# check for negative weight cycles. If path obtained from above step (shortest distances)
		# is shorter, there's a cycle. So quit.
		for u, v, w in self.graph:
		 	if dist[u] != float("Inf") and dist[u] + w < dist[v]:
		 		print("Negative Cycles !")
		 		return
		# print distances
		self.printArr(dist)
# dry run
if __name__ == "__main__":
	g = Graph(5)
	g.addEdge(0, 1, -1)
	g.addEdge(0, 2, 4)
	g.addEdge(1, 2, 3)
	g.addEdge(1, 3, 2)
	g.addEdge(1, 4, 2)
	g.addEdge(3, 2, 5)
	g.addEdge(3, 1, 1)
	g.addEdge(4, 3, -3)
	g.bellmanFord(0)

PHP


<?php 
/*Part of Cosmos by OpenGenus Foundation*/
/*{source, destination, distance}*/
$edges =    array(
           array(0,1,5),
           array(0,2,8),
           array(0,3,-4),
           array(1,0,-2),
           array(2,1,-3),
           array(2,3,9),
           array(3,1,7),
           array(3,4,2),
           array(4,0,6),
           array(4,2,7),
       );
BellmanFord($edges,10,5,4);
function BellmanFord($edges, $edgecount, $nodecount, $source) { 
    // Initialize distances
    $distances = array();
    // This is the initialize single source function.
    for($i =0; $i < $nodecount; ++$i)
      $distances[$i]= INF;
      $distances[$source]=0;
     // Do what we are suppose to do, This is the BellmanFord function
     for($i =0; $i < $nodecount;++$i) {
         $somethingChanged =false;
         for($j =0; $j < $edgecount;++$j) {
             if($distances[$edges[$j][0]]!= INF) { 
                 $newDist = $distances[$edges[$j][0]]+ $edges[$j][2];
                if($newDist < $distances[$edges[$j][1]]) { 
                     $distances[$edges[$j][1]]= $newDist;
                     $somethingChanged =true;
                }
            }
        }
       // If $somethingChanged == FALSE, then nothing has changed and we can go on with the next step.
       if(!$somethingChanged)break;
    }
   // Check the graph for negative weight cycles
   for($i =0; $i < $edgecount;++$i) {
        if($distances[$edges[$i][1]] > $distances[$edges[$i][0]]+ $edges[$i][2]){
            echo "Negative edge weight cycle detected!";
            return;
        }
    }
   // Print out the shortest distance
    for($i =0; $i < $nodecount;++$i) {
        echo "Shortest distance between nodes ". $source . " and ". $i ." is ". $distances[$i];
        echo "<br>";
    }
   return;
}
?>

Applications

The applications of Bellman-Ford Algorithm are:

Bellman-Ford Algorithm works without the full network view/ knowledge and thus, can be used in distance vector algorithms.
Running Dijkstra's algorithm requires full knowledge of all edges and weights in the network. Unlike link state routing algorithms, distance vector algorithms do not construct such a full network map. Thus, Bellman-Ford Algorithm is superior to Dijkstra's Algorithm in this case.
Bellman-Ford Algorithm terminates upon finding a negative cycle and hence, can be used to detect it.
It is used in cycle-cancelling techniques in network flow analysis.