Dijkstra’s Algorithm in C++ Using Priority Queue

Dijkstra’s Algorithm is one of the most important and widely used algorithms for finding the shortest path in a weighted graph with non-negative edges. In this blog post, we’ll implement Dijkstra’s algorithm using a priority queue (min-heap) in C++. The input will be in the form of an edge list, and the algorithm will return the shortest distance from a source node to all other nodes.

Dijkstra’s Algorithm in C++ Using Priority Queue

// User Function Template
class Solution {
  public:
    vector<int> dijkstra(int V, vector<vector<int>> &edges, int src) {
        // Code here
        vector<int> t(V,INT_MAX);
        vector<vector<pair<int,int>>> adj(V);
        for(int i=0;i<edges.size();i++){
            int u=edges[i][0];
            int v=edges[i][1];
            int cost=edges[i][2];
            adj[u].push_back({cost,v});
            adj[v].push_back({cost,u});
        }
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
        q.push({0,src});
        t[src]=0;
        while(!q.empty()){
            int node=q.top().second;
            int curd=q.top().first;
            q.pop();
            for(int i=0;i<adj[node].size();i++){
                int newnode=adj[node][i].second;
                int newd=adj[node][i].first;
                if(curd+newd<t[newnode]){
                    t[newnode]=curd+newd;
                    q.push({t[newnode],newnode});
                }
            }
        }
        return t;
    }
};

Input Format

• V: Number of vertices in the graph.

• edges: A vector of vectors, where each subvector contains 3 integers: {u, v, weight} representing an undirected edge between u and v with the given weight.

• src: The starting node from which to calculate shortest paths.

Output

Returns a vector of integers representing the minimum distance from the source to every other node.

Sample Input
V = 5
edges = {
{0, 1, 4},
{0, 2, 1},
{2, 1, 2},
{1, 3, 1},
{2, 3, 5},
{3, 4, 3}
}
src = 0

Sample Output
0 3 1 4 7