C++ Program to Implement Bellman Ford 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. }

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.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.