Bellman-Ford Algorithm in C and C++

Here you will learn about Bellman-Ford Algorithm in C and C++.

Dijkstra and Bellman-Ford Algorithms used to find out single source shortest paths. i.e. there is a source node, from that node we have to find shortest distance to every other node. Dijkstra algorithm fails when graph has negative weight cycle. But Bellman-Ford Algorithm won’t fail even, the graph has negative edge cycle. If there any negative edge cycle it will detect and say there is negative edge cycle. If not it will give answer to given problem.

Bellman-Ford Algorithm will work on logic that, if graph has n nodes, then shortest path never contain more than n-1 edges. This is exactly what Bellman-Ford do. It is enough to relax each edge (v-1) times to find shortest path. But to find whether there is negative cycle or not we again do one more relaxation. If we get less distance in nth relaxation we can say that there is negative edge cycle. Reason for this is negative value added and distance get reduced.

Relaxing edge

In algorithm and code below we use this term Relaxing edge.

Relaxing edge is an operation performed on an edge (u, v) . when,

d(u) > d(v) + Cost(u,v)

Here d(u) means distance of u. If already known distance to “u” is greater than the path from “s” to “v” and “v” to “u” we update that d(u) value with d(v) + cost(u,v).

Algorithm and Time Complexity

Bellman-Ford (G,w,S){   //G is graph given, W is weight matrix, S is source vertex (starting vertex)
    Initialize single source (G,S)  //means initially distance to every node is infinity except to source. Source is 0 (zero). This will take O(v) time

    For i=1 to |G.V| -1     //Runs (v-1) times
        For each edge (G,V)€ G.E    // E times
            Relax(u,v,w)    //O(1) time

    For each edge (G,V) € G.E
        If (v.d > u.d + w(u,v))     //The idea behind this is we are relaxing edges nth time if we found more shortest path than (n-1)th level, we can say that graph is having negative edge cycle and detected.
            Return False

    return true
}

Finally time complexity is (v-1) (E) O(1) = O(VE)

Example Problem

This is the given directed graph.

(s,t) = 6  (y,x) = -3

(s,y)= 7  (y,z) = 9

(t,y) = 8  (x,t) = -2

(t,z) = -4  (z,x) = 7

(t,x) = 5  (z,s) = 2

Above we can see using vertex “S” as source (Setting distance as 0), we initialize all other distance as infinity.

	S	T	X	Y	Z
distance	0	∞	∞	∞	∞
Path	–	–	–	–	–

Table and Image explanation: This table, 2nd row shows distance from source to that particular node ad 3rd row shows to reach that node what is the node we visited recently. This path we can see in the image also.

Note: In each iteration, iteration “n” means it contains the path at most “n” edges. And while we are doing iteration “n” we must follow the graph which we obtained in iteration “n-1”.

Iteration 1: edge (s,t) and (z,y) relaxed and updating the distances to t and y.

	S	T	X	Y	Z
distance	0	6	∞	7	∞
Path	–	S	–	S	–

Iteration 2 : edge (t,z) and (y,x) relaxed and x and z values are updated.

	S	T	X	Y	Z
distance	0	6	4	7	2
Path	–	S	Y	S	T

Iteration 3: Value of t updated by relaxing (x,t)

	S	T	X	Y	Z
distance	0	2	4	7	2
Path	–	X	Y	S	T

Iteration 4: Value of z updated by relaxing edge (t,z)

Until now 4 iterations completed and shortest path found to every node form source node. Now we have to do one more iteration to find whether there exists negative edge cycle or not. When we do this nth (5th here) relaxation if we found less distance to any vertex from any other path we can say that there is negative edge cycle. Here we can relax any edge to graph which obtained in iteration 4and we can observe that there is no chance to change those values. So we can confirm that there is no negative edge cycle in this graph.

Program for Bellman-Ford Algorithm in C

Code explanation

This picture shows the Structure of our input graph.

We create a structure called “Graph” which contains two integers int v (represent number of vertices) and int E (represents number of edges) and also another structure inside this structure which represents edge. That structure contains 3 integers source, destination, weight of that edge. So we create “E” number of structures inside the structure Graph.

After creating Graph, choose a source node and send to BellmanFord function. In this function we relax each edge “v-1” times. After this we can store the result of shortest paths in an array. And we do one more relaxation to find whether there exists negative edge cycle or not. If we got less distance at any node in Vth relaxation of edges, then we can say that the graph have negative edge cycle.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct Edge
{
    // This structure is equal to an edge. Edge contains two end points. These edges are directed edges so they
	//contain source and destination and some weight. These 3 are elements in this structure
    int source, destination, weight;
};

// a structure to represent a connected, directed and weighted graph
struct Graph
{
    int V, E;
	// V is number of vertices and E is number of edges

    struct Edge* edge;
	// This structure contain another structure which we already created edge.
};

struct Graph* createGraph(int V, int E)
{
    struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph));
	//Allocating space to structure graph

    graph->V = V;   //assigning values to structure elements that taken form user.

    graph->E = E;

    graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );
	//Creating "Edge" type structures inside "Graph" structure, the number of edge type structures are equal to number of edges

    return graph;
}

void FinalSolution(int dist[], int n)
{
	// This function prints the final solution
    printf("\nVertex\tDistance from Source Vertex\n");
    int i;

    for (i = 0; i < n; ++i){
		printf("%d \t\t %d\n", i, dist[i]);
	}
}

void BellmanFord(struct Graph* graph, int source)
{
    int V = graph->V;

    int E = graph->E;

    int StoreDistance[V];

    int i,j;

    // This is initial step that we know , we initialize all distance to infinity except source.
	// We assign source distance as 0(zero)

    for (i = 0; i < V; i++)
        StoreDistance[i] = INT_MAX;

    StoreDistance[source] = 0;

    //The shortest path of graph that contain V vertices, never contain "V-1" edges. So we do here "V-1" relaxations
    for (i = 1; i <= V-1; i++)
    {
        for (j = 0; j < E; j++)
        {
            int u = graph->edge[j].source;

            int v = graph->edge[j].destination;

            int weight = graph->edge[j].weight;

            if (StoreDistance[u] + weight < StoreDistance[v])
                StoreDistance[v] = StoreDistance[u] + weight;
        }
    }

    // Actually upto now shortest path found. But BellmanFord checks for negative edge cycle. In this step we check for that
    // shortest distances if graph doesn't contain negative weight cycle.

    // If we get a shorter path, then there is a negative edge cycle.
    for (i = 0; i < E; i++)
    {
        int u = graph->edge[i].source;

        int v = graph->edge[i].destination;

        int weight = graph->edge[i].weight;

        if (StoreDistance[u] + weight < StoreDistance[v])
            printf("This graph contains negative edge cycle\n");
    }

    FinalSolution(StoreDistance, V);

    return;
}

int main()
{
    int V,E,S;  //V = no.of Vertices, E = no.of Edges, S is source vertex

	printf("Enter number of vertices in graph\n");
    scanf("%d",&V);

	printf("Enter number of edges in graph\n");
    scanf("%d",&E);

	printf("Enter your source vertex number\n");
	scanf("%d",&S);

    struct Graph* graph = createGraph(V, E);    //calling the function to allocate space to these many vertices and edges

    int i;
    for(i=0;i<E;i++){
        printf("\nEnter edge %d properties Source, destination, weight respectively\n",i+1);
        scanf("%d",&graph->edge[i].source);
        scanf("%d",&graph->edge[i].destination);
        scanf("%d",&graph->edge[i].weight);
    }

    BellmanFord(graph, S);
	//passing created graph and source vertex to BellmanFord Algorithm function

    return 0;
}

Output

Enter number of vertices in graph
5
Enter number of edges in graph
10
Enter your source vertex number
0

Enter edge 1 properties Source, destination, weight respectively
0 1 6

Enter edge 2 properties Source, destination, weight respectively
0 2 7

Enter edge 3 properties Source, destination, weight respectively
1 2 8

Enter edge 4 properties Source, destination, weight respectively
1 4 -4

Enter edge 5 properties Source, destination, weight respectively
1 3 5

Enter edge 6 properties Source, destination, weight respectively
3 1 -2

Enter edge 7 properties Source, destination, weight respectively
2 3 -3

Enter edge 8 properties Source, destination, weight respectively
2 4 9

Enter edge 9 properties Source, destination, weight respectively
4 0 2

Enter edge 10 properties Source, destination, weight respectively
4 3 7

Vertex  Distance from Source Vertex
0  0
1  2
2  7
3  4
4  -2

Program for Bellman-Ford Algorithm in C++

#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

using namespace std;

struct Edge
{
    // This structure is equal to an edge. Edge contains two end points. These edges are directed edges so they
	//contain source and destination and some weight. These 3 are elements in this structure
    int source, destination, weight;
};

// a structure to represent a connected, directed and weighted graph
struct Graph
{
    int V, E;
	// V is number of vertices and E is number of edges

    struct Edge* edge;
	// This structure contain another structure which we already created edge.
};

struct Graph* createGraph(int V, int E)
{
    struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph));
	//Allocating space to structure graph

    graph->V = V;   //assigning values to structure elements that taken form user.

    graph->E = E;

    graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );
	//Creating "Edge" type structures inside "Graph" structure, the number of edge type structures are equal to number of edges

    return graph;
}

void FinalSolution(int dist[], int n)
{
	// This function prints the final solution
    cout<<"\nVertex\tDistance from Source Vertex\n";
    int i;

    for (i = 0; i < n; ++i){
		cout<<i<<"\t\t"<<dist[i]<<"\n";
	}
}

void BellmanFord(struct Graph* graph, int source)
{
    int V = graph->V;

    int E = graph->E;

    int StoreDistance[V];

    int i,j;

    // This is initial step that we know , we initialize all distance to infinity except source.
	// We assign source distance as 0(zero)

    for (i = 0; i < V; i++)
        StoreDistance[i] = INT_MAX;

    StoreDistance[source] = 0;

    //The shortest path of graph that contain V vertices, never contain "V-1" edges. So we do here "V-1" relaxations
    for (i = 1; i <= V-1; i++)
    {
        for (j = 0; j < E; j++)
        {
            int u = graph->edge[j].source;

            int v = graph->edge[j].destination;

            int weight = graph->edge[j].weight;

            if (StoreDistance[u] + weight < StoreDistance[v])
                StoreDistance[v] = StoreDistance[u] + weight;
        }
    }

    // Actually upto now shortest path found. But BellmanFord checks for negative edge cycle. In this step we check for that
    // shortest distances if graph doesn't contain negative weight cycle.

    // If we get a shorter path, then there is a negative edge cycle.
    for (i = 0; i < E; i++)
    {
        int u = graph->edge[i].source;

        int v = graph->edge[i].destination;

        int weight = graph->edge[i].weight;

        if (StoreDistance[u] + weight < StoreDistance[v])
            cout<<"\nThis graph contains negative edge cycle\n";
    }

    FinalSolution(StoreDistance, V);

    return;
}

int main()
{
    int V,E,S;  //V = no.of Vertices, E = no.of Edges, S is source vertex

	cout<<"Enter number of vertices in graph\n";
    cin>>V;

	cout<<"Enter number of edges in graph\n";
    cin>>E;

	cout<<"Enter your source vertex number\n";
	cin>>S;

    struct Graph* graph = createGraph(V, E);    //calling the function to allocate space to these many vertices and edges

    int i;
    for(i=0;i<E;i++){
        cout<<"\nEnter edge "<<i+1<<" properties Source, destination, weight respectively\n";
        cin>>graph->edge[i].source;
        cin>>graph->edge[i].destination;
        cin>>graph->edge[i].weight;
    }

    BellmanFord(graph, S);
	//passing created graph and source vertex to BellmanFord Algorithm function

    return 0;
}

Reference: Introduction to Algorithms by Thomas H. Cormen

Comment below if you have queries or found anything incorrect in above tutorial for Bellman-Ford Algorithm in C and C++.