Bellman Ford Algorithm in C with Implementation

Bellman Ford Algorithm in C is used in the graph data structure to find the shortest route from a single source to every other node in the Graph. There are many more uses of the Bellman ford algorithm other than finding the shortest route/path such as Bellman-Ford can detect the presence of a negative-weight cycle in the graph itself.

Bellman ford works on graph data structure, the graph data structure is a linkage of nodes with help of edges and these edges have some weights attached to them, representing the distance or the cost to move from one node to another.

Problem Description

Write a C program to find shortest path using bellman ford algorithm.

Problem Solution

Problem Statement: Find the least cost route from a to b, c, d, and e nodes. If weights are cost to move from one node to another node. Here source node is ‘a,’ and the destination nodes are b, c, d, and e.

Solution: Bellman ford algorithm is a dynamic programming-based algorithm.

In this case, we use previously known values to identify a more optimal solution ahead.

Assume we have a graph represented by an adjacency matrix with |vertices| number of vertices and a list with edge information such as its source and destination nodes, which is indicated by the *HEAD pointer. We must find the shortest path from the source node to the destination node.

Steps to Find the Shortest Path using Bellman Ford Algorithm in C:

First initialize the shortest path array to store the shortest path from the source node to each node in the graph. This shortest-path array is of size |vertices|.
Then store INT_MAX to each element in the shortest path array.
Initialize shortest_path[source]=0 as from source node to source node the cost is 0.
Now we need to process the edges |vertives-1| times.
Traverse each edge and see if the sum of the shortest path from the source node to that node and the cost to move from the edge’s source node to the destination node is less than the shortest path from the source node to that Edge’s destination node. This process is known as the relaxation and it is done |vertives-1| times.

Program/Source Code

Here is source code of the C Program to Implement Bellmanford Algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C program to Implement Bellmanford Algorithm

```
 */
```
```
 
```
```
#include<stdio.h>
```
```
#include<limits.h>
```
```
#include<stdlib.h>
```
```
 
```

// Step 1 we are here initializing the node in the map.

// It has source node data and the destination node along with the weight of the edge.

```
struct Edge
```
```
{
```
```
    int source;
```
```
    int destination;
```
```
    struct Egde *next;
```
```
};
```
```
 
```

// Step 2: This is the pointer that points to the list that contains the edges list.

```
 
```
```
struct Edge *HEAD=NULL;
```
```
void Insert_Edge(int, int);
```
```
 
```
```
int main()
```
```
{
```
```
    int vertices;
```

    // Here we are initializing the total number of nodes in the graph

```
    vertices = 5;
```
```
    int graph[vertices][vertices];
```
```
 
```

    // Here we initialised the weight to be infinite at first

```
    for(int i=0;i<vertices;i++)
```
```
    {
```
```
        for(int j=0;j<vertices;j++)
```
```
        {
```
```
            graph[i][j]=INT_MAX;
```
```
        }
```
```
    }
```
```
 
```
```
    // Add edges in the node 
```
```
    graph[0][1]=200;
```
```
    graph[0][2]=-20;
```
```
    graph[0][3]=100;
```
```
    graph[1][4]=70;
```
```
    graph[2][3]=50;
```
```
    graph[3][4]=10;
```
```
    graph[4][2]=40;
```
```
 
```

    // This will print the graph in adjacency matrix form.

    // We are using an adjacency matrix for representing the graph.

    printf("GRAPH AFTER FILLING THE NODE IS :::\n");

```
    for(int i=0;i<vertices;i++)
```
```
    {
```
```
        for(int j=0;j<vertices;j++)
```
```
        {
```
```
            if(graph[i][j] == INT_MAX)
```
```
            {
```
```
                printf("%-10c", '-');
```
```
            }
```
```
            else
```
```
            {
```

                printf("%-10d", graph[i][j]);

```
            }
```
```
        }
```
```
        printf("\n");
```
```
    }
```
```
 
```

    printf("**********************************************************************\n");

    // Inserting edges in the linked list.

```
    for(int i=0;i<vertices;i++)
```
```
    {
```
```
        for(int j=0;j<vertices;j++)
```
```
        {
```
```
            if(graph[i][j] != INT_MAX)
```
```
            {
```
```
                Insert_Edge(i,j);
```
```
            }
```
```
        }
```
```
    }
```
```
    int source;
```

    printf("Enter the source node::  ");

```
 
```

    //source is the node from where the cost is to be found for all other nodes.

    scanf("%d",&source); // Choose the source as 0 for our first test case.

```
    int shortest_path[vertices];
```
```
    for(int i=0;i<vertices;i++)
```
```
    {
```
```
        shortest_path[i]=INT_MAX;
```
```
    }
```

    shortest_path[source]=0; //As Source cost to itself is 0

```
 
```

    // This Loop Runs |VERTICES-1| Times

```
    for(int i=1;i<vertices;i++)
```
```
    {
```
```
        struct Edge *temp=HEAD; 
```
```
        while(temp!=NULL)
```
```
        {
```

            //here we check if the node is reachable from the source vertex or not.

            if(shortest_path[temp->source] != INT_MAX)

```
            {
```

                if(shortest_path[temp->source] + graph[temp->source][temp->destination]

                < shortest_path[temp->destination])

```
                {
```

                    shortest_path[temp->destination]=shortest_path[temp->source]

                    + graph[temp->source][temp->destination];

```
                }
```
```
            }
```
```
            temp= temp->next;
```
```
        }
```
```
    }
```

    printf("MINUMUM COSTS FOUND AFTER APPLYING THE BELLMAN FORD ALGORITHM

            FOR SOURCE NODE [%c] COMES OUT TO BE::: \n",source+97);

    printf("*****************************************************************\n");

```
    for(int i=0;i<vertices;i++)
```
```
    {
```
```
        if(shortest_path[i]==INT_MAX)
```
```
        {
```

            printf("Node [%c] to [%c] is unreachable \n",source+97,i+97);

```
            continue;
```
```
        }
```
```
        else
```
```
        {
```

            printf("Node [%c] TO [%c] MINIMUM COST IS:: %d\n",source+97,i+97,shortest_path[i]);

```
        }
```
```
    }
```
```
    return 0;
```
```
}
```
```
void Insert_Edge(int src, int des)
```
```
{
```

    struct Edge *ptr = (struct Edge*)malloc(sizeof(struct Edge));

```
    struct Edge *temp=HEAD;
```
```
    ptr->source=src;
```
```
    ptr->destination=des;
```
```
    if(HEAD==NULL)
```
```
    {
```
```
        HEAD=ptr;
```
```
        HEAD->next=NULL;
```
```
    }
```
```
    else
```
```
    {
```
```
        while(temp->next!=NULL)
```
```
        {
```

            temp=(struct Edge*)temp->next;

```
        }
```
```
        temp->next=ptr;
```
```
        ptr->next=NULL;
```
```
    }
```
```
    return ;
```
```
}
```

Program Explanation

1. First declare the structure to carry the edges in the linked list. It has values of source node, destination node and weight between them.
2. Then initialize an adjacency matrix with a 5 * 5 matrix (*5->vertices in the matrix).
3. Then fill the edges and store the edges in the list pointed by the head pointer.
4. The head pointer points to the linked list of edges.
5. Print the graph i.e., adjacency matrix.
6. In the adjacency matrix, the row represents the source node and the columns represent the destination nodes in the graph.
7. Then declare the shortest path array, which records the shortest path from the source vertex to all other vertexes in the graph. Initially, all are set to INT MAX. We set the shortest path from the source node to the source node to zero.
8. Then we iterate the process of relaxing the shortest path array with the help of edges list |vertex-1| times.
9. In the inner loop, we have iterated the linked list containing the edge information.
10. Update the value in the shortest path array if we get a smaller value in the relaxation process for any particular node.
11. Relaxation process is discussed in the algorithm approach clearly.
12. At the end we get the minimized path from the source vertex to each vertex.
13. Print the vertex in character format by using the %c format specifier. Since the ‘0’ node represents the ‘a’ node in the graph, we can convert 0 to a by adding 97 to the 0 and then printing it with the %c format specifier.
14. ‘1’ can be added to 97 and resent ‘b’. Likewise we iterated the loop and printed all the shortest paths from the source vertex.

Time Complexity: O(|Vertices -1 | * number of Edges)
Outer loop runs as many vertices are there in the graph, we also relaxation process that requires all the edges to be iterated. Thus, we conclude that the bellman ford algorithm’s time complexity is O(|Vertices -1 | * number of Edges). We can minimize the time complexity of this algorithm if we find that no change is happened after two successive iterations in the outer loop, as it shows we have reached the optimized solution.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Space Complexity: O(vertices * vertices + Edges)
we stored the graph in the 2-d adjacency matrix, which takes up quadratic space and we even made a link list to accommodate the edges in it.

Runtime Test Cases

Testcase 1: In this case, we have taken the source vertex as “a” vertex. So the source node to find the shortest path using bellman ford algorithm is “0”.

 
GRAPH AFTER FILLING THE NODE IS :::
-         200       -20       100       -         
-         -         -         -         70        
-         -         -         50        -         
-         -         -         -         10        
-         -         40        -         -         
**************************************************************************************************
Enter the source node::  0
MINUMUM COSTS FOUND AFTER APPLYING THE BELLMAN FORD ALGORITHM FOR SOURCE NODE [a] COMES OUT TO BE::: 
**************************************************************************************************
Node [a] TO [a] MINIMUM COST IS:: 0
Node [a] TO [b] MINIMUM COST IS:: 200
Node [a] TO [c] MINIMUM COST IS:: -20
Node [a] TO [d] MINIMUM COST IS:: 30
Node [a] TO [e] MINIMUM COST IS:: 40

Testcase 2: In this case, we have taken the source vertex as “e” vertex. So the source node to find the shortest path using bellman ford algorithm is “4”.

GRAPH AFTER FILLING THE NODE IS :::
-         200       -20       100       -         
-         -         -         -         70        
-         -         -         50        -         
-         -         -         -         10        
-         -         40        -         -         
****************************************************************************************************
Enter the source node::  4
MINUMUM COSTS FOUND AFTER APPLYING THE BELLMAN FORD ALGORITHM FOR SOURCE NODE [e] COMES OUT TO BE::: 
****************************************************************************************************
Node [e] to [a] is unreachable 
Node [e] to [b] is unreachable 
Node [e] TO [c] MINIMUM COST IS:: 40
Node [e] TO [d] MINIMUM COST IS:: 90
Node [e] TO [e] MINIMUM COST IS:: 0

Testcase 3: In this case, we have taken the source vertex as “b” vertex. So the source node to find the shortest path using bellman ford algorithm is “1”.

GRAPH AFTER FILLING THE NODE IS :::
-         200       -20       100       -         
-         -         -         -         70        
-         -         -         50        -         
-         -         -         -         10        
-         -         40        -         -         
***************************************************************************************************
Enter the source node::  1
MINUMUM COSTS FOUND AFTER APPLYING THE BELLMAN FORD ALGORITHM FOR SOURCE NODE [b] COMES OUT TO BE::: 
***************************************************************************************************
Node [b] to [a] is unreachable 
Node [b] TO [b] MINIMUM COST IS:: 0
Node [b] TO [c] MINIMUM COST IS:: 110
Node [b] TO [d] MINIMUM COST IS:: 160
Node [b] TO [e] MINIMUM COST IS:: 70

Points to Remember:

Bellman ford algorithm fails if the graph has a negative weighted cycle in it.
It works fine even if we have negative weights on the edges of the graph as long as it is not a part of a cycle.

Method 2: Implementation of Bellmanford Algorithm

This is a C Program to find shortest path using bellman ford algorithm. Given a graph and a source vertex src in graph, find shortest paths from src to all vertices in the given graph. The graph may contain negative weight edges. We have discussed Dijkstra’s algorithm for this problem. Dijksra’s algorithm is a Greedy algorithm and time complexity is O(VLogV) (with the use of Fibonacci heap). Dijkstra doesn’t work for Graphs with negative weight edges, Bellman-Ford works for such graphs. Bellman-Ford is also simpler than Dijkstra and suites well for distributed systems. But time complexity of Bellman-Ford is O(VE), which is more than Dijkstra.

Program/Source Code

Here is source code of the C Program to Implement Bellmanford Algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
#include <string.h>
```
```
#include <limits.h>
```
```
 
```
```
int i, j;
```

// a structure to represent a weighted edge in graph

```
struct Edge
```
```
{
```
```
    int src, dest, weight;
```
```
};
```
```
 
```

// a structure to represent a connected, directed and weighted graph

```
struct Graph
```
```
{
```

    // V-> Number of vertices, E-> Number of edges

```
    int V, E;
```
```
 
```

    // graph is represented as an array of edges.

```
    struct Edge* edge;
```
```
};
```
```
 
```

// Creates a graph with V vertices and E edges

```
struct Graph* createGraph(int V, int E)
```
```
{
```

    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));

```
    graph->V = V;
```
```
    graph->E = E;
```
```
 
```

    graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge));

```
 
```
```
    return graph;
```
```
}
```
```
 
```

// A utility function used to print the solution

```
void printArr(int dist[], int n)
```
```
{
```

    printf("Vertex   Distance from Source\n");

```
    for (i = 0; i < n; ++i)
```

        printf("%d \t\t %d\n", i, dist[i]);

```
}
```
```
 
```

// The main function that finds shortest distances from src to all other

// vertices using Bellman-Ford algorithm.  The function also detects negative

```
// weight cycle
```

void BellmanFord(struct Graph* graph, int src)

```
{
```
```
    int V = graph->V;
```
```
    int E = graph->E;
```
```
    int dist[V];
```
```
 
```

    // Step 1: Initialize distances from src to all other vertices as INFINITE

```
    for (i = 0; i < V; i++)
```
```
        dist[i] = INT_MAX;
```
```
    dist[src] = 0;
```
```
 
```

    // Step 2: Relax all edges |V| - 1 times. A simple shortest path from src

    // to any other vertex can have at-most |V| - 1 edges

```
    for (i = 1; i <= V - 1; i++)
```
```
    {
```
```
        for (j = 0; j < E; j++)
```
```
        {
```
```
            int u = graph->edge[j].src;
```

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

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

            if (dist[u] != INT_MAX && dist[u] + weight < dist[v])

                dist[v] = dist[u] + weight;

```
        }
```
```
    }
```
```
 
```

    // Step 3: check for negative-weight cycles.  The above step guarantees

    // shortest distances if graph doesn't contain negative weight cycle.

    // If we get a shorter path, then there is a cycle.

```
    for (i = 0; i < E; i++)
```
```
    {
```
```
        int u = graph->edge[i].src;
```
```
        int v = graph->edge[i].dest;
```

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

        if (dist[u] != INT_MAX && dist[u] + weight < dist[v])

            printf("Graph contains negative weight cycle");

```
    }
```
```
 
```
```
    printArr(dist, V);
```
```
 
```
```
    return;
```
```
}
```
```
 
```

// Driver program to test above functions

```
int main()
```
```
{
```

    /* Let us create the graph given in above example */

    int V = 5; // Number of vertices in graph

    int E = 8; // Number of edges in graph

    struct Graph* graph = createGraph(V, E);

```
 
```

    // add edge 0-1 (or A-B in above figure)

```
    graph->edge[0].src = 0;
```
```
    graph->edge[0].dest = 1;
```
```
    graph->edge[0].weight = -1;
```
```
 
```

    // add edge 0-2 (or A-C in above figure)

```
    graph->edge[1].src = 0;
```
```
    graph->edge[1].dest = 2;
```
```
    graph->edge[1].weight = 4;
```
```
 
```

    // add edge 1-2 (or B-C in above figure)

```
    graph->edge[2].src = 1;
```
```
    graph->edge[2].dest = 2;
```
```
    graph->edge[2].weight = 3;
```
```
 
```

    // add edge 1-3 (or B-D in above figure)

```
    graph->edge[3].src = 1;
```
```
    graph->edge[3].dest = 3;
```
```
    graph->edge[3].weight = 2;
```
```
 
```

    // add edge 1-4 (or A-E in above figure)

```
    graph->edge[4].src = 1;
```
```
    graph->edge[4].dest = 4;
```
```
    graph->edge[4].weight = 2;
```
```
 
```

    // add edge 3-2 (or D-C in above figure)

```
    graph->edge[5].src = 3;
```
```
    graph->edge[5].dest = 2;
```
```
    graph->edge[5].weight = 5;
```
```
 
```

    // add edge 3-1 (or D-B in above figure)

```
    graph->edge[6].src = 3;
```
```
    graph->edge[6].dest = 1;
```
```
    graph->edge[6].weight = 1;
```
```
 
```

    // add edge 4-3 (or E-D in above figure)

```
    graph->edge[7].src = 4;
```
```
    graph->edge[7].dest = 3;
```
```
    graph->edge[7].weight = -3;
```
```
 
```
```
    BellmanFord(graph, 0);
```
```
 
```
```
    return 0;
```
```
}
```

Runtime Test Cases

$ gcc BellmanFord.c
$ ./a.out
 
Vertex   Distance from Source
0 		 0
1 		 -1
2 		 2
3 		 -2
4 		 1

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Find the Transitive Closure of a Graph using Warshall’s Algorithm

» Next - C Program to Perform AVL Tree Operations

Related Posts:

Recommended Articles: