C++ Program to Implement Bellmanford Algorithm

«
»
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.

  1. /*
  2.  * C++ Program to Implement Bellmanford Algorithm
  3.  */
  4. #include<iostream>
  5. #include<stdio.h>
  6. using namespace std;
  7. #include<conio.h>
  8. #define INFINITY 999
  9. struct node
  10. {
  11.     int cost;
  12.     int value;
  13.     int from;
  14. }a[5];
  15. void addEdge(int am[][5],int src,int dest,int cost)
  16. {
  17.      am[src][dest] = cost;
  18.      return;
  19. }
  20. void bell(int am[][5])
  21. {
  22.     int i, j, k, c = 0, temp;
  23.     a[0].cost = 0;
  24.     a[0].from = 0;
  25.     a[0].value = 0;
  26.     for (i = 1; i < 5; i++)
  27.     {
  28.         a[i].from = 0;
  29.         a[i].cost = INFINITY;
  30.         a[i].value = 0;
  31.     }
  32.     while (c < 5)
  33.     {
  34.         int min = 999;
  35.         for (i = 0; i < 5; i++)
  36.         {
  37.             if (min > a[i].cost && a[i].value == 0)
  38.             {
  39.                 min = a[i].cost;
  40.             }
  41.             else
  42.             {
  43.                 continue;
  44.             }
  45.         }
  46.         for (i = 0; i < 5; i++)
  47.         {
  48.             if (min == a[i].cost && a[i].value == 0)
  49.             {
  50.                 break;
  51.             }
  52.             else
  53.             {
  54.                 continue;
  55.             }
  56.         }
  57.         temp = i;
  58.         for (k = 0; k < 5; k++)
  59.         {
  60.             if (am[temp][k] + a[temp].cost < a[k].cost)
  61.             {
  62.                 a[k].cost = am[temp][k] + a[temp].cost;
  63.                 a[k].from = temp;
  64.             }
  65.             else
  66.             {
  67.                 continue;
  68.             }
  69.         }
  70.         a[temp].value = 1;
  71.         c++;
  72.     }
  73.     cout<<"Cost"<<"\t"<<"Source Node"<<endl; 
  74.     for (j = 0; j < 5; j++)
  75.     {
  76.         cout<<a[j].cost<<"\t"<<a[j].from<<endl;
  77.     }
  78. }
  79. int main()
  80. {
  81.     int n, am[5][5], c = 0, i, j, cost;
  82.     for (int i = 0; i < 5; i++)
  83.     {
  84.         for (int j = 0; j < 5; j++)
  85.         {
  86.             am[i][j] = INFINITY;
  87.         }
  88.     }
  89.     while (c < 8)
  90.     {
  91.         cout<<"Enter the source, destination and cost of edge\n";
  92.         cin>>i>>j>>cost;
  93.         addEdge(am, i, j, cost);
  94.         c++;
  95.     }
  96.     bell(am);
  97.     getch();
  98. }

advertisement
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
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn