Bellman-Ford Algorithm in C and C++

Here you will find out about the Bellman-Ford Algorithm in C and C++.

Dijkstra and Bellman-Ford Algorithms used to discover single source most limited ways.

for example, there is a sourcing hub, from that hub we need to discover most limited separation

to each other hub. Dijkstra algorithm bombs when the chart has a negative weight cycle. However,

Bellman-Ford Algorithm won’t bomb even, the diagram has a negative edge cycle. On the off chance

that there any negative edge cycle it will recognize and state there is a negative edge cycle. If not it will offer a response to a given issue.

Bellman-Ford Algorithm will chip away at the rationale that, in the event that chart has n hubs,

at that point most limited way never contain more than n-1 edges. This is actually what Bellman-Ford do.

It is sufficient to loosen up each edge (v-1) times to discover the briefest way. In any case, to

discover whether there is a negative cycle or not we again do one more unwinding.

In the event that we get less separation in nth unwinding, we can say that there is a negative edge cycle.

The explanation behind this is negative worth included and separation get decreased.

Loosening up edge

In algorithm and code beneath we utilize this term Relaxing edge.

Loosening up edge is an activity performed on an edge (u, v) . when,

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

Here d(u) implies separation of u. In the event that definitely known separation to “u” is

more prominent than the way from “s” to “v” and “v” to “u” we update that d(u) esteem 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
}

At last time multifaceted nature is (v-1) (E) O(1) = O(VE)

Example Problem

Bellman-Ford Algorithm

This is the given coordinated diagram.

(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 utilizing vertex “S” as source (Setting separation as 0), we instate all other separation as unendingness.

Table and Image clarification: This table, the second column shows good ways from source to

that specific hub advertisement third line shows to arrive at that hub what is the hub we visited as of late.

This way we can find in the picture moreover.

Note: In every cycle, emphasis “n” signifies it contains the way at most “n” edges. And keeping in

mind that we are doing cycle “n” we should pursue the diagram which we got in emphasis “n-1”.

Emphasis 1: edge (s,t) and (z,y) loose and refreshing the separations to t and y.

Emphasis 2: edge (t,z) and (y,x) loose and x and z esteems are refreshed.

Emphasis 3: Value of t refreshed by unwinding (x,t)

Emphasis 4: Value of z refreshed by loosening up edge (t,z)

As of not long ago, 4 emphases finished and most limited way found to each hub structure source hub.

Presently we need to do one more emphasis to discover whether there exists negative edge cycle or not.

At the point when we do this nth (fifth here) unwinding in the event that we discovered less separation to any

vertex from some other way, we can say that there is a negative edge cycle. Here we can loosen up any edge

to chart which acquired in emphasis 4and we can see that there is no way to change those qualities.

So we can affirm that there is no negative edge cycle in this diagram.

Program for Bellman-Ford Algorithm in C

Code clarification

This image shows the Structure of our information diagram.

We make a structure called “Chart” which contains two whole numbers int v (speak to a number of vertices) and

int E (speaks to a number of edges) and furthermore another structure inside this structure which speaks to edge.

That structure contains 3 whole numbers source, goal, the weight of that edge. So we make “E” number of structures inside the structure Graph.

In the wake of making Graph, pick a sourcing hub and send to BellmanFord work. In this

capacity, we loosen up each edge “v-1” times. After this, we can store the consequence of

briefest ways in an exhibit. What’s more, we do one more unwinding to discover whether there

exists negative edge cycle or not. In the event that we got less separation at any hub in Vth unwinding of edges,

at that point we can say that the diagram has a 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

Remark underneath on the off chance that you have questions or discovered anything off

base in the above instructional exercise for Bellman-Ford Algorithm in C and C++.