C++ Program to Implement Dijkstra’s Algorithm Using Queue

«
»
This is a C++ Program to implement Dijkstra’s Shortest path algorithm using Queue.

Here is source code of the C++ Program to Implement Dijkstra’s Algorithm Using Queue. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <cstdio>
  2. #include <queue>
  3. #include <vector>
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. #define MAX 100001
  9. #define INF (1<<20)
  10. #define pii pair< int, int >
  11. #define pb(x) push_back(x)
  12.  
  13. struct comp
  14. {
  15.         bool operator()(const pii &a, const pii &b)
  16.         {
  17.             return a.second > b.second;
  18.         }
  19. };
  20.  
  21. priority_queue<pii, vector<pii > , comp> Q;
  22. vector<pii > G[MAX];
  23. int D[MAX];
  24. bool F[MAX];
  25.  
  26. int main()
  27. {
  28.     int i, u, v, w, sz, nodes, edges, starting;
  29.  
  30.     // create graph
  31.     cout << "Enter the number of vertices and edges: ";
  32.     cin >> nodes >> edges;
  33.     cout << "Enter the edges with weigth: <source> <destination> <weigth>: \n";
  34.     for (i = 0; i < edges; i++)
  35.     {
  36.         cin >> u >> v >> w;
  37.         G[u].pb(pii(v, w));
  38.         G[v].pb(pii(u, w)); // for undirected
  39.     }
  40.     cout << "Enter the source node: ";
  41.     cin >> starting;
  42.  
  43.     // initialize distance vector
  44.     for (i = 1; i <= nodes; i++)
  45.         D[i] = INF;
  46.     D[starting] = 0;
  47.     Q.push(pii(starting, 0));
  48.  
  49.     // dijkstra
  50.     while (!Q.empty())
  51.     {
  52.         u = Q.top().first;
  53.         Q.pop();
  54.         if (F[u])
  55.             continue;
  56.         sz = G[u].size();
  57.         for (i = 0; i < sz; i++)
  58.         {
  59.             v = G[u][i].first;
  60.             w = G[u][i].second;
  61.             if (!F[v] && D[u] + w < D[v])
  62.             {
  63.                 D[v] = D[u] + w;
  64.                 Q.push(pii(v, D[v]));
  65.             }
  66.         }
  67.         F[u] = 1; // done with u
  68.     }
  69.  
  70.     // result
  71.     for (i = 1; i <= nodes; i++)
  72.         cout << "Node " << i << ", min weight = " << D[i] << endl;
  73.     return 0;
  74. }

Output:

advertisement
$ g++ DijkstraUsingQueue.cpp
$ a.out
 
Enter the number of vertices and edges: 6
7
Enter the edges with weigth: <source> <destination> <weigth>: 
0 1 1
1 2 3
1 4 5
3 4 7
4 5 9
5 3 8
0 3 3
Enter the source node: 1
Node 1, min weight = 0
Node 2, min weight = 3
Node 3, min weight = 12
Node 4, min weight = 5
Node 5, min weight = 14
Node 6, min weight = 1048576
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

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.