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.

```
#include <cstdio>
```
```
#include <queue>
```
```
#include <vector>
```
```
#include <iostream>
```
```
 
```
```
using namespace std;
```
```
 
```
```
#define MAX 100001
```
```
#define INF (1<<20)
```
```
#define pii pair< int, int >
```
```
#define pb(x) push_back(x)
```
```
 
```
```
struct comp
```
```
{
```

        bool operator()(const pii &a, const pii &b)

```
        {
```
```
            return a.second > b.second;
```
```
        }
```
```
};
```
```
 
```

priority_queue<pii, vector<pii > , comp> Q;

```
vector<pii > G[MAX];
```
```
int D[MAX];
```
```
bool F[MAX];
```
```
 
```
```
int main()
```
```
{
```

    int i, u, v, w, sz, nodes, edges, starting;

```
 
```
```
    // create graph
```

    cout << "Enter the number of vertices and edges: ";

```
    cin >> nodes >> edges;
```

    cout << "Enter the edges with weigth: <source> <destination> <weigth>: \n";

```
    for (i = 0; i < edges; i++)
```
```
    {
```
```
        cin >> u >> v >> w;
```
```
        G[u].pb(pii(v, w));
```

        G[v].pb(pii(u, w)); // for undirected

```
    }
```
```
    cout << "Enter the source node: ";
```
```
    cin >> starting;
```
```
 
```
```
    // initialize distance vector
```
```
    for (i = 1; i <= nodes; i++)
```
```
        D[i] = INF;
```
```
    D[starting] = 0;
```
```
    Q.push(pii(starting, 0));
```
```
 
```
```
    // dijkstra
```
```
    while (!Q.empty())
```
```
    {
```
```
        u = Q.top().first;
```
```
        Q.pop();
```
```
        if (F[u])
```
```
            continue;
```
```
        sz = G[u].size();
```
```
        for (i = 0; i < sz; i++)
```
```
        {
```
```
            v = G[u][i].first;
```
```
            w = G[u][i].second;
```

            if (!F[v] && D[u] + w < D[v])

```
            {
```
```
                D[v] = D[u] + w;
```
```
                Q.push(pii(v, D[v]));
```
```
            }
```
```
        }
```
```
        F[u] = 1; // done with u
```
```
    }
```
```
 
```
```
    // result
```
```
    for (i = 1; i <= nodes; i++)
```

        cout << "Node " << i << ", min weight = " << D[i] << endl;

```
    return 0;
```
```
}
```

Output:

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

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

« Prev - C++ Program to Check the Connectivity of Directed Graph Using BFS

» Next - C++ Program to Check if a Graph is Strongly Connected or Not

Related Posts:

Recommended Articles: