The gist of Bellman-Ford single source shortest path algorithm is a below :
Below data structures are used for storing the graph before running Bellman-Ford algorithm
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 do 3. For every edge E in the EdgeList do 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.
C++
Python : Bellman-Ford’s shortest path algorithm in Python 3
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 BellmanFordShortestPath(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)+") : "+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.BellmanFordShortestPath(source_node)
Output of Bellman-Ford’s shortest path algorithm implemented in Python 3
Source Node(0) -> Destination Node(0) : 0
Source Node(0) -> Destination Node(1) : -1
Source Node(0) -> Destination Node(2) : 0
Source Node(0) -> Destination Node(3) : -3
Source Node(0) -> Destination Node(4) : 1
Source Node(0) -> Destination Node(5) : -3