C++ Program to Implement Dijkstra’s Algorithm using Priority_queue(Heap)

«
»
This C++ program displays the Djikstra’s Algorithm of finding shortest paths from one node to others using the concept of a priority queue. a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a “priority” associated with it.

Here is the source code of the C++ program to display the shortest distance and the source node associated with the shortest distance. 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 Dijkstra's Algorithm using Priority_queue(Heap)
  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[7];
  15. void min_heapify(int *b, int i, int n)
  16. {
  17.     int j, temp;
  18.     temp = b[i];
  19.     j = 2 * i;
  20.     while (j <= n)
  21.     {
  22.         if (j < n && b[j + 1] < b[j])
  23.         {
  24.             j = j + 1;
  25.         }
  26.         if (temp < b[j])
  27.         {
  28.             break;
  29.         }
  30.         else if (temp >= b[j])
  31.         {
  32.             b[j / 2] = b[j];
  33.             j = 2 * j;
  34.         }
  35.     }
  36.     b[j / 2] = temp;
  37.     return;
  38. }
  39. void build_minheap(int *b, int n)
  40. {
  41.     int i;
  42.     for(i = n / 2; i >= 1; i--)
  43.     {
  44.         min_heapify(b, i, n);
  45.     }
  46. }
  47. void addEdge(int am[][7], int src, int dest, int cost)
  48. {
  49.      am[src][dest] = cost;
  50.      return;
  51. }
  52. void bell(int am[][7])
  53. {
  54.     int i, j, k, c = 0, temp;
  55.     a[0].cost = 0;
  56.     a[0].from = 0;
  57.     a[0].value = 0;
  58.     for (i = 1; i < 7; i++)
  59.     {
  60.         a[i].from = 0;
  61.         a[i].cost = INFINITY;
  62.         a[i].value = 0;
  63.     }
  64.     while (c < 7)
  65.     {
  66.         int min = 999;
  67.         for (i = 0; i < 7; i++)
  68.         {
  69.             if (min > a[i].cost && a[i].value == 0)
  70.             {
  71.                 min = a[i].cost;
  72.             }
  73.             else
  74.             {
  75.                 continue;
  76.             }
  77.         }
  78.         for (i = 0; i < 7; i++)
  79.         {
  80.             if (min == a[i].cost && a[i].value == 0)
  81.             {
  82.                 break;
  83.             }
  84.             else
  85.             {
  86.                 continue;
  87.             }
  88.         }
  89.         temp = i;
  90.         for (k = 0; k < 7; k++)
  91.         {
  92.             if (am[temp][k] + a[temp].cost < a[k].cost)
  93.             {
  94.                 a[k].cost = am[temp][k] + a[temp].cost;
  95.                 a[k].from = temp;
  96.             }
  97.             else
  98.             {
  99.                 continue;
  100.             }
  101.         }
  102.         a[temp].value = 1;
  103.         c++;
  104.     }
  105.     cout<<"Cost"<<"\t"<<"Source Node"<<endl; 
  106.     for (j = 0; j < 7; j++)
  107.     {
  108.         cout<<a[j].cost<<"\t"<<a[j].from<<endl;
  109.     }
  110. }
  111. int main()
  112. {
  113.     int n, am[7][7], c = 0, i, j, cost;
  114.     for (int i = 0; i < 7; i++)
  115.     {
  116.         for (int j = 0; j < 7; j++)
  117.         {
  118.             am[i][j] = INFINITY;
  119.         }
  120.     }
  121.     while (c < 12)
  122.     {
  123.         cout<<"Enter the source, destination and cost of edge\n";
  124.         cin>>i>>j>>cost;
  125.         addEdge(am, i, j, cost);
  126.         c++;
  127.     }
  128.     bell(am);
  129.     getch();
  130. }

advertisement
Output
 
Enter the source, destination and cost of edge
0
1
3
Enter the source, destination and cost of edge
0
2
6
Enter the source, destination and cost of edge
1
2
2
Enter the source, destination and cost of edge
1
3
4
Enter the source, destination and cost of edge
2
3
1
Enter the source, destination and cost of edge
2
4
4
Enter the source, destination and cost of edge
2
5
2
Enter the source, destination and cost of edge
3
4
2
Enter the source, destination and cost of edge
3
6
4
Enter the source, destination and cost of edge
4
6
1
Enter the source, destination and cost of edge
4
5
2
Enter the source, destination and cost of edge
5
6
1
Cost    Source Node
0       0
3       0
5       1
6       2
8       3
7       2
8       5

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