What is the most simple & efficient C++ code for Dijkstra's shortest path algorithm?

When I used to Dijkstra, it was like this: https://www.topcoder.com/community/data-science/data-science-tutorials/power-up-c-with-the-standard-template-library-part-2/#dijkstra1

Here is a version with map and setvoid preprocess(const vector<vector<int>>& G, int src, unordered_map<int,int>& vmap, map<int,unordered_set<int>>& dmap){int V = G.size();for(int i = 0; i < V; i++){vmap[i] = INT_MAX;}vmap[src] = 0;for(int i = 0; i < V; i++){if(i!=src)dmap[INT_MAX].insert(i);}dmap[0].insert(src);}void sp(const vector<vector<int>>& G, int src){int V = G.size();unordered_map<int,int> vmap;map<int,unordered_set<int>> dmap;preprocess(G, src, vmap, dmap);unordered_set<int> snodes;unordered_map<int, int> rmap;while(snodes.size() != V){int d = dmap.begin()->first;int v = *(dmap[d].begin());for(int i = 0; i < V; i++){if(G[v][i] != 0 && vmap.count(i)){if(vmap[i] > G[v][i] + d){int k = vmap[i];vmap[i] = G[v][i] + d;dmap[k].erase(i);dmap[vmap[i]].insert(i);}}}vmap.erase(v);snodes.insert(v);dmap[d].erase(v);rmap[v] = d;if(dmap[d].size() == 0){dmap.erase(d);}}for(pair<int,int> p : rmap){cout << p.first << " " << p.second << endl;}}

This is how I usually code it : void Solve() { memset(dist, kInf, sizeof dist); dist[1] = 0; q.emplace(1, 0); while (!q.empty()) { int node = q.top().node; int cost = q.top().cost; q.pop(); if (cost != dist[node]) continue; for (auto it : G[node]) { int new_dist = cost + it.second; if (new_dist < dist[it.first]) { dist[it.first] = new_dist; q.emplace(it.first, new_dist); } } } }

Here is the simplest implentation :1.Using priority queue container in C++ STL. // Time complexity : O(ElogV) #include <bits/stdc++.h> using namespace std; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector< pii > vii; #define INF 0x3f3f3f3f vii *G; // Graph vi Dist; // for storing the distance of every other node from source. /*==========================================*/ void Dijkstra(int source, int N) { priority_queue<pii> Q; Dist.assign(N,INF); Dist[source] = 0; Q.push({0,source}); while(!Q.empty()){ int u = Q.top().second; Q.pop(); for(auto &c : G[u]){ int v = c.first; int w = c.second; if(Dist[v] > Dist[u]+w){ Dist[v] = Dist[u]+w; Q.push({Dist[v],v}); } } } } /*===========================================*/ int main() { int N, M, u, v, w, source; // N-total no of nodes, M-no. of edges, cin >> N >> M; // u,v and w are the end vertices and the weight associated with an edge G = new vii[N+1]; for(int i=0;i<M;++i){ cin >> u >> v >> w; G[u].push_back({v,w}); G[v].push_back({u,w}); } cin >> source; Dijkstra(source,N); for(int i=0;i<N;i++) cout<<Dist[i]<<" "; cout<<endl; return 0; } 2. Using set container in C++ STL. /* Dijkstra algorithm for Undirected Graph, time complexity : O(|E|.log|V|) */ #include <bits/stdc++.h> using namespace std; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector< pii > vii; #define INF 0x3f3f3f3f vii *G; // Graph vi D; // distance vector for storing min distance from the source. /*=======================================*/ void dijkstra(int source, int N) { D.assign(N,INF); D[source] = 0; set<pii> Q; Q.insert({0,source}); while(!Q.empty()) { auto top = Q.begin(); int u = top->second; Q.erase(top); for(auto next: G[u]) { int v = next.first, weight = next.second; if( D[v] > D[u] + weight) { if(Q.find( {D[v], v} ) != Q.end()) Q.erase(Q.find( {D[v], v} )); D[v] = D[u] + weight; Q.insert( {D[v], v} ); } } } } /*==========================================*/ int main(){ int N,M,source,u,v,w; cin >> N >> M >> source; //Input the number of nodes(0 based), number of edges and the source vertex. G = new vii[N]; for(int i=0;i<M;i++){ cin >> u >> v >> w; //Input the starting vertex of the edge, the ending vertex and the cost of the edge. G[u].push_back({v,w}); G[v].push_back({u,w}); } dijkstra(source, N); for(int i=0;i<N;i++) cout<<D[i]<<" "; cout<<endl; }

Following are the links to my GitHub for Dijkstra's Algorithm - 1. Using Brute Force  (Running Time of O(mn) ) - https://github.com/harshch1803/Algorithms/blob/master/Graph%20Algorithms/Dijkastra's%20Algorithm/DijkstraAlgo%20(2).cpp 2.Using Priority Queue (Running Time of O(mlogn) - https://github.com/harshch1803/Algorithms/blob/master/Graph%20Algorithms/Dijkastra's%20Algorithm/Dijkstra_Heap.cpp 3.Using Set (Running Time of O(mlogn) - https://github.com/harshch1803/Algorithms/blob/master/Graph%20Algorithms/Dijkastra's%20Algorithm/Dijkstra_Set.cpp Well the lines of my code are more than most of the answers here . But my aim is to make it as readable as possible at the expense of the lines of code.

Use STL-Set #include <bits/stdc++.h> using namespace std; #define N 1000000 #define INF 2000000001 typedef long long int lli; typedef pair<lli,int> ii; int n, m, S, D; vector<ii> G[N]; lli dist[N]; void Input() { ifstream fcin; fcin.open("input.txt"); int i, v1, v2; lli w; fcin>>n>>m>>S>>D; for(i=0; i<m; i++) { fcin>>v1>>v2>>w; G[v1].push_back(ii(w,v2)); G[v2].push_back(ii(w,v1)); } fcin.close(); } void Solve() { int i, v, vi; lli cost, dv; set<ii> djk; ii u; //initialize for(i=0; i<N; i++) dist[i] = INF; dist[S] = 0; djk.insert(ii(0,S)); //apply Dijkstra's algo while(!djk.empty()) { u = *djk.begin(); djk.erase(u); v = u.second; dv = u.first; for(i=0; i<G[v].size(); i++) { vi = G[v][i].second; cost = G[v][i].first; if(dv + cost < dist[vi]) { if(dist[vi] != INF) { djk.erase(djk.find(ii(dist[vi],vi))); } dist[vi] = dv + cost; djk.insert(ii(dist[vi], vi)); } } } } void Print() { ofstream fcout; fcout.open("output.txt"); fcout<<dist[D]<<endl; fcout.close(); } int main() { Input(); Solve(); Print(); return 0; }

I found the algorithm to be intuitive enough but the implementation got tricky due to the nature of STL priority queue. I used multiset and ran it against the sample graph on geeksforgeeks and it seems to be working fine. struct dcomp{ bool operator()(pair<int, int> a, pair<int, int> b){ return a.second < b.second; } }; struct Graph_d{ int V; vector<vector<pair<int, int>>> adj; multiset<pair<int, int>, dcomp> dset; vector<pair<int, int>> result; Graph_d(){} Graph_d(int v) :V(v){ adj.resize(V); } void addEdge(int src, int dst, int cost){ adj[src].push_back({ dst, cost }); adj[dst].push_back({ src, cost }); } void getresult(int src){ sort(result.begin(), result.end(), [](pair<int, int> a, pair<int, int> b)->bool{return a.first < b.first; }); cout << "Vertex\tDistance from source(" << src << ")\n"; for (int i = 0; i < result.size(); ++i) cout << result[i].first << "\t" << result[i].second << endl; } void dijkstra(int src){ for (int i = 0; i < V; ++i){ if (i == src) dset.insert({ src, 0 }); else dset.insert({ i, numeric_limits<int>::max() }); } while (!dset.empty()){ //1. get the top vertex, one which has minimum cost int topvertex = dset.begin()->first; int topcost = dset.begin()->second; result.push_back({ topvertex, topcost }); dset.erase(dset.begin()); //2. find if its neighbors are in the set and update cost if required for (auto adj_it = adj[topvertex].begin(); adj_it != adj[topvertex].end(); ++adj_it){ int nbr = adj_it->first; auto dset_it = find_if(dset.begin(), dset.end(), [nbr](pair<int, int> a)->bool{return nbr == a.first; }); if (dset_it != dset.end() && dset_it->second > topcost + adj_it->second ){ //neighbor exists in set and cost update is necessary dset.insert({ dset_it->first, topcost + adj_it->second }); dset.erase(dset_it); } } } getresult(src); } }; void test_Dijkstra(){ Graph_d g(9); g.addEdge(0, 1, 4); g.addEdge(0, 7, 8); g.addEdge(1, 2, 8); g.addEdge(1, 7, 11); g.addEdge(2, 3, 7); g.addEdge(2, 8, 2); g.addEdge(2, 5, 4); g.addEdge(3, 4, 9); g.addEdge(3, 5, 14); g.addEdge(4, 5, 10); g.addEdge(5, 6, 2); g.addEdge(6, 7, 1); g.addEdge(6, 8, 6); g.addEdge(7, 8, 7); g.dijkstra(0); }

This site helped me a lot to write a simpe Dijkstra. You can see how it works and the code it goes through (click on the left menu "Dijkstra's algorithm")  :) http://visualgo.net/sssp.html# http://visualgo.net

http://en.wikipedia.org/wiki/Dijkstra's_algorithm You can use the priority_queue STL for the heap. http://stackoverflow.com/questions/19535644/how-to-use-the-priority-queue-stl-for-objects http://stackoverflow.com/questions/2974470/efficiency-of-the-stl-priority-queue #include <cstdio> #include <iostream> #include <vector> #include <climits> #include <queue> using namespace std; vector < vector <int> > graph; vector < vector <int> > weight; vector < int> cost; int N; struct cmp { bool operator()(const int &lhs, const int &rhs) const { return cost[lhs] > cost[rhs]; } }; int min(int a,int b) { if(a<b) return a; return b; } priority_queue <int,vector<int>,cmp> pq; int dijkstra(int from,int to) { vector <bool> visited(N,false); visited[from] = true; cost [from] = 0; pq.push(from); while(!pq.empty() && !visited[to]) { int current = pq.top(); pq.pop(); visited[current] = true; for(int i=0;i<graph[current].size();i++) { if(!visited[graph[current][i]]) { cost[graph[current][i]] = min( cost[graph[current][i]] ,cost[current] + weight[current][i]); pq.push(graph[current][i]); } } } return cost[to]; } int main() { int n,a,b,c; cin>>n; N = n; for(int i=0;i<n;i++) { graph.push_back(vector <int> ()); weight.push_back(vector <int> ()); cost.push_back(INT_MAX); } cin>>a>>b>>c; while(a!=-1 || b!=-1) { graph[a].push_back(b); weight[a].push_back(c); cin>>a>>b>>c; } cin>>a>>b; while(a!=-1 || b!=-1) { cout<<dijkstra(a,b)<<endl; cin>>a>>b; } } Sample input/output 5 0 1 1 0 4 3 1 2 2 2 3 3 4 3 2 -1 -1 -1 0 3 5 0 2 3