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 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.

Bellman_Ford_Shortest_Path

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

© 2019-2026 Algotree.org | All rights reserved.

This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org

"First, solve the problem. Then, write the code. - John Johnson"