Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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.
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.
