Bellman Ford Algorithm in C++

This C++ program implements the Bellmanford Algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.

Here is the source code of the C++ program to display the shortest path costs along with the intermediate node paths taken on giving the source node, destination node and cost of node as inputs. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

```
/*
```

 * C++ Program to Implement Bellmanford Algorithm

```
 */
```
```
#include<iostream>
```
```
#include<stdio.h>
```
```
using namespace std;
```
```
#include<conio.h>
```
```
#define INFINITY 999
```
```
struct node
```
```
{
```
```
    int cost;
```
```
    int value;
```
```
    int from;
```
```
}a[5];
```

void addEdge(int am[][5],int src,int dest,int cost)

```
{
```
```
     am[src][dest] = cost;
```
```
     return;
```
```
}
```
```
void bell(int am[][5])
```
```
{
```
```
    int i, j, k, c = 0, temp;
```
```
    a[0].cost = 0;
```
```
    a[0].from = 0;
```
```
    a[0].value = 0;
```
```
    for (i = 1; i < 5; i++)
```
```
    {
```
```
        a[i].from = 0;
```
```
        a[i].cost = INFINITY;
```
```
        a[i].value = 0;
```
```
    }
```
```
    while (c < 5)
```
```
    {
```
```
        int min = 999;
```
```
        for (i = 0; i < 5; i++)
```
```
        {
```

            if (min > a[i].cost && a[i].value == 0)

```
            {
```
```
                min = a[i].cost;
```
```
            }
```
```
            else
```
```
            {
```
```
                continue;
```
```
            }
```
```
        }
```
```
        for (i = 0; i < 5; i++)
```
```
        {
```

            if (min == a[i].cost && a[i].value == 0)

```
            {
```
```
                break;
```
```
            }
```
```
            else
```
```
            {
```
```
                continue;
```
```
            }
```
```
        }
```
```
        temp = i;
```
```
        for (k = 0; k < 5; k++)
```
```
        {
```

            if (am[temp][k] + a[temp].cost < a[k].cost)

```
            {
```

                a[k].cost = am[temp][k] + a[temp].cost;

```
                a[k].from = temp;
```
```
            }
```
```
            else
```
```
            {
```
```
                continue;
```
```
            }
```
```
        }
```
```
        a[temp].value = 1;
```
```
        c++;
```
```
    }
```

    cout<<"Cost"<<"\t"<<"Source Node"<<endl;

```
    for (j = 0; j < 5; j++)
```
```
    {
```

        cout<<a[j].cost<<"\t"<<a[j].from<<endl;

```
    }
```
```
}
```
```
int main()
```
```
{
```
```
    int n, am[5][5], c = 0, i, j, cost;
```
```
    for (int i = 0; i < 5; i++)
```
```
    {
```
```
        for (int j = 0; j < 5; j++)
```
```
        {
```
```
            am[i][j] = INFINITY;
```
```
        }
```
```
    }
```
```
    while (c < 8)
```
```
    {
```

        cout<<"Enter the source, destination and cost of edge\n";

```
        cin>>i>>j>>cost;
```
```
        addEdge(am, i, j, cost);
```
```
        c++;
```
```
    }
```
```
    bell(am);
```
```
    getch();
```
```
}
```

Output
 
Enter the source, destination and cost of edge
0
1
-1
Enter the source, destination and cost of edge
0
2
4
Enter the source, destination and cost of edge
1
2
3
Enter the source, destination and cost of edge
1
3
2
Enter the source, destination and cost of edge
3
1
1
Enter the source, destination and cost of edge
1
4
2
Enter the source, destination and cost of edge
4
3
-3
Enter the source, destination and cost of edge
3
2
5
Cost    Source Node
0       0
-1      0
2       1
-2      4
1       1

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Find Number of Articulation Points in a Graph

» Next - C++ Program to Implement Dijkstra’s Algorithm using Priority Queue

Related Posts:

Recommended Articles: