Bellman-Ford Shortest Path Algorithm
The gist of Bellman-Ford single source shortest path algorithm is a below :
- Bellman-Ford algorithm finds the shortest path ( in terms of distance / cost ) from a single source in a directed, weighted graph containing positive and negative edge weights.
- Bellman-Ford algorithm performs edge relaxation of all the edges for every node. Bellman-Ford Edge Relaxation If ( distance-from-source-to [ node_v ] > distance-from-source-to [ node_u ] + weight-of-path-from-node-u-to-v ) then distance-from-source-to [ node_v ] = distance-from-source-to [ node_u ] + weight-of-path-from-node-u-to-v )
- With negative edge weights in a graph Bellman-Ford algorithm is preferred over Dijkstra’s algorithm as Dijkstra’s algorithm cannot handle negative edge weights in a graph.
Below data structures are used for storing the graph before running Bellman-Ford algorithm
- EdgeList : List of all the edges in the graph.
- EdgeWeight : Map of edges and their corresponding weights.
Algorithm : Bellman-Ford Single Source Shortest Path ( EdgeList, EdgeWeight )
1. Initialize the distance from the source node S to all other nodes as infinite (999999999) and to itself as 0. Distance [ AllNodes ] = 999999999, Distance [ S ] = 0. 2. For every node in the graph 3. For every edge E in the EdgeList 4. Node_u = E.first, Node_v = E.second 5. Weight_u_v = EdgeWeight ( Node_u, Node_v ) 6. If ( Distance [ v ] > Distance [ u ] + Weight_u_v ) 7. Distance [ v ] = Distance [ u ] + Weight_u_v
Example of single source shortest path from source node 0 using Bellman-Ford algorithm
Note: Weight of the path corresponds to the distance / cost between the nodes.
Bellman-Ford iteration 1 Dist [ 0 ] = 0. Distance from source node 0 to itself is 0. Dist [ 1 ] = Dist [ 2 ] = Dist [ 3 ] = Dist [ 4 ] = Dist [ 5 ] = 999999999. Initialize the distance from the source node 0 to all other nodes to a max value (ex:999999999).
| Node CountIteration | Edge (U-V) | Weight (Cost/Distance) of Edge (U-V) | Distance from source to node ‘U’ | Distance from source to node ‘V’ | Update |
|---|---|---|---|---|---|
| 1 | ( 0 - 1 ) | -1 | Dist [ 0 ] = 0 | Dist [ 1 ] = 999999999 | If : Dist [ 1 ] > Dist [ 0 ] + ( -1 ) Yes Update : Dist [ 1 ] = 0 + -1 = -1 |
| 1 | ( 0 - 5 ) | 2 | Dist [ 0 ] = 0 | Dist [ 5 ] = 999999999 | If : Dist [ 5 ] > Dist [ 0 ] + ( 2 ) Yes Update : Dist [ 5 ] = 0 + 2 = 2 |
| 1 | ( 1 - 2 ) | 2 | Dist [ 1 ] = -1 | Dist [ 2 ] = 999999999 | If : Dist [ 2 ] > Dist [ 1 ] + ( 2 ) Yes Update : Dist [ 2 ] = -1 + 2 = 1 |
| 1 | ( 1 - 5 ) | -2 | Dist [ 1 ] = -1 | Dist [ 5 ] = 2 | If : Dist [ 5 ] > Dist [ 1 ] + ( -2 ) Yes Update : Dist [ 5 ] = -1 + -2 = -3 |
| 1 | ( 2 - 3 ) | 5 | Dist [ 2 ] = 1 | Dist [ 3 ] = 999999999 | If : Dist [ 3 ] > Dist [ 2 ] + ( 5 )Yes Update : Dist [ 3 ] = 1 + 5 = 6 |
| 1 | ( 2 - 4 ) | 1 | Dist [ 2 ] = 1 | Dist [ 4 ] = 999999999 | If : Dist [ 4 ] > Dist [ 2 ] + ( 1 )Yes Update : Dist [ 4 ] = 1 + 1 = 2 |
| 1 | ( 4 - 3 ) | -4 | Dist [ 4 ] = 2 | Dist [ 3 ] = 6 | If : Dist [ 3 ] > Dist [ 4 ] + ( -4 )Yes Update : Dist [ 3 ] = 6 + (-4) = 2 |
| 1 | ( 4 - 5 ) | 3 | Dist [ 4 ] = 2 | Dist [ 5 ] = -3 | If : Dist [ 5 ] > Dist [ 4 ] + ( 3 )No No change : Dist [ 5 ] = -3 |
| 1 | ( 5 - 1 ) | 2 | Dist [ 5 ] = -3 | Dist [ 1 ] = -1 | If : Dist [ 1 ] > Dist [ 5 ] + ( 2 )No No change : Dist [ 1 ] = -1 |
| 1 | ( 5 - 2 ) | 3 | Dist [ 5 ] = -3 | Dist [ 2 ] = 1 | If : Dist [ 2 ] > Dist [ 5 ] + ( 3 )Yes Update Dist [ 2 ] = -3 + 3 = 0 |
… the algorithm continues with iterations 2, 3, 4, 5 and 6 (number of nodes). During each iteration the shortest path from source node to other nodes is updated.
Graph type : Designed for directed graph containing positive and negative edge weights. Time complexity of Bellman-Ford’s algorithm : O ( E . V ). V is the number of vertices and E is the number of edges in a graph.
Bellman-Ford’s shortest implementation
class Edge :
def __init__(self, src, dst, weight) :
self.src = src
self.dst = dst
self.weight = weight
class Graph :
def __init__(self, edge_list, node_cnt) :
self.edge_list = edge_list
self.node_cnt = node_cnt
def BellmanFord (self, src) :
# Initialize the distance from the source node S to all other nodes as infinite (999999999) and to itself as 0.
distance = [999999999999] * self.node_cnt
distance[src] = 0
for node in range(self.node_cnt) :
for edge in self.edge_list :
if (distance[edge.dst] > distance[edge.src] + edge.weight) :
distance[edge.dst] = distance[edge.src] + edge.weight
for edge in self.edge_list :
if (distance[edge.dst] > distance[edge.src] + edge.weight) :
print("Negative weight cycle exist in the graph")
for node in range(self.node_cnt) :
print("Source Node("+str(src)+") -> Destination Node("+str(node)+") : Length => "+str(distance[node]))
def main() :
e01 = Edge(0, 1, -1)
e05 = Edge(0, 5, 2)
e12 = Edge(1, 2, 2)
e15 = Edge(1, 5, -2)
e23 = Edge(2, 3, 5)
e24 = Edge(2, 4, 1)
e43 = Edge(4, 3, -4)
e45 = Edge(4, 5, 3)
e51 = Edge(5, 1, 2)
e52 = Edge(5, 2, 3)
edge_list = [e01, e05, e12, e15, e23, e24, e43, e45, e51, e52]
node_cnt = 6
source_node = 0
g = Graph(edge_list, node_cnt)
g.BellmanFord(source_node)
if __name__ == "__main__":
main()
Output
Source Node(0) -> Destination Node(0) : Length => 0
Source Node(0) -> Destination Node(1) : Length => -1
Source Node(0) -> Destination Node(2) : Length => 0
Source Node(0) -> Destination Node(3) : Length => -3
Source Node(0) -> Destination Node(4) : Length => 1
Source Node(0) -> Destination Node(5) : Length => -3
#include<iostream>
#include<vector>
#include<list>
using namespace std;
class Edge {
public :
Edge(int arg_src, int arg_dst, int arg_weight) : src(arg_src), dst(arg_dst), weight(arg_weight)
{}
int src;
int dst;
int weight;
};
class Graph {
private :
int node_count;
list<Edge> edge_list;
public:
Graph (int arg_node_count, list<Edge> arg_edge_list) : node_count(arg_node_count), edge_list(arg_edge_list)
{}
void BellmanFord (int src) {
// Initialize the distance / cost from the source node to all other nodes to some max value.
vector<int> distance(node_count, 999999999);
// Distance/cost from the source node to itself is 0.
distance[src] = 0;
for (int i=0; i<node_count; i++) {
for (auto& it : edge_list) {
if (distance[it.dst] > distance[it.src] + it.weight) {
distance[it.dst] = distance[it.src] + it.weight;
}
}
}
for (auto& it : edge_list) {
if (distance[it.dst] > distance[it.src] + it.weight) {
cout << "Negative weight cycle exist in the graph !!!" << endl;
}
}
for (int i=0; i<node_count; i++)
cout << "Source Node(" << src << ") -> Destination Node(" << i << ") : Length => " << distance[i] << endl;
}
};
int main(){
Edge e01(0, 1, -1);
Edge e05(0, 5, 2);
Edge e12(1, 2, 2);
Edge e15(1, 5, -2);
Edge e23(2, 3, 5);
Edge e24(2, 4, 1);
Edge e43(4, 3, -4);
Edge e45(4, 5, 3);
Edge e51(5, 1, 2);
Edge e52(5, 2, 3);
int node_count = 6;
int source_node = 0;
list<Edge> edge_list = { e01, e05, e12, e15, e23, e24, e43, e45, e51, e52 };
Graph g(node_count, edge_list);
g.BellmanFord(source_node);
return 0;
}
Output
Source Node(0) -> Destination Node(0) : Length => 0
Source Node(0) -> Destination Node(1) : Length => -1
Source Node(0) -> Destination Node(2) : Length => 0
Source Node(0) -> Destination Node(3) : Length => -3
Source Node(0) -> Destination Node(4) : Length => 1
Source Node(0) -> Destination Node(5) : Length => -3
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
class Edge {
Edge(int arg_src, int arg_dst, int arg_weight) {
this.src = arg_src;
this.dst = arg_dst;
this.weight = arg_weight;
}
int src;
int dst;
int weight;
}
class Graph {
int node_count;
List<Edge> edge_list;
Graph (int arg_node_count, List<Edge> arg_edge_list) {
this.node_count = arg_node_count;
this.edge_list = arg_edge_list;
}
void BellmanFord (int src) {
// Initialize the distance/cost from the source node to all other nodes to some max value.
Long INF = (long) 999999999;
List<Long> distance = new ArrayList<Long>(Collections.nCopies(node_count, INF));
// Distance/cost from the source node to itself is 0.
distance.set(src, (long) 0);
for (int i=0; i<node_count; i++) {
for (Edge it : edge_list) {
if (distance.get(it.dst) > distance.get(it.src) + it.weight) {
distance.set(it.dst, distance.get(it.src) + it.weight);
}
}
}
for (Edge it : edge_list) {
if (distance.get(it.dst) > distance.get(it.src) + it.weight) {
System.out.println("Negative weight cycle exist in the graph !!!");
}
}
for (int i=0; i<node_count; i++)
System.out.println("Source Node(" + src + ") -> Destination Node(" + i + ") : Length => " + distance.get(i));
}
public static void main (String[] args) {
Edge e01 = new Edge(0, 1, -1);
Edge e05 = new Edge(0, 5, 2);
Edge e12 = new Edge(1, 2, 2);
Edge e15 = new Edge(1, 5, -2);
Edge e23 = new Edge(2, 3, 5);
Edge e24 = new Edge(2, 4, 1);
Edge e43 = new Edge(4, 3, -4);
Edge e45 = new Edge(4, 5, 3);
Edge e51 = new Edge(5, 1, 2);
Edge e52 = new Edge(5, 2, 3);
int node_count = 6;
int source_node = 0;
List<Edge> edge_list = new ArrayList<>();
Collections.addAll(edge_list, e01, e05, e12, e15, e23, e24, e43, e45, e51, e52);
Graph g = new Graph(node_count, edge_list);
g.BellmanFord(source_node);
}
}
Output
Source Node(0) -> Destination Node(0) : Length => 0
Source Node(0) -> Destination Node(1) : Length => -1
Source Node(0) -> Destination Node(2) : Length => 0
Source Node(0) -> Destination Node(3) : Length => -3
Source Node(0) -> Destination Node(4) : Length => 1
Source Node(0) -> Destination Node(5) : Length => -3