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

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. }

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

If you find any mistake above, kindly email to [email protected]

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 & discussions at Telegram SanfoundryClasses.