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 betweenu
andv
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