Algotree > Algorithms > Single Source Shortest Path > Bellman-Ford Shortest Path Algorithm implementation in Python and C++

Bellman-Ford Shortest Path Algorithm implementation in Python and C++

Bellman-Ford Single Source Shortest Path

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) {
distance-from-source-to [node_v] = distance-from-source-to [node_u] + weight-of-path-from-node-u-to-v)
}
In presence of 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 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

Bellman_Ford_Graph_Image

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 Count (Iteration)	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++

C++ Implementation of Bellman-Ford's shortest path algorithm in C++14

#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 distanceance/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 << ") : " << 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) : 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

Python : Implementation of 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