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.
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.
Related Posts:
- Practice Computer Science MCQs
- Practice Programming MCQs
- Check Computer Science Books
- Check C++ Books
- Apply for C++ Internship