### n8118's blog

By n8118, history, 5 years ago, I have learnt Dijkstra's recently and couldn't implement it effectively. Can some one post your Dijkstra's algo implementation in (c or c++) using stl's. I will use it as reference to implement my code. Thanks in advance.. c++, Comments (32)
 »
 » Hello, You can try this question : EZDIJKST, it's a direct implementation of the algorithm. You can refer My Solution which uses STL set for reference.
 » This is my typical implementation of Dijkstra using C++11 and priority_queue: Dijkstra (this code finds the shortest path from node 1 to all other nodes)
•  » » why you use if(dis>d[u]) continue?
•  » » » Because otherwise it would simply be a BFS that keeps going only when new distance would be lower than current minimum distance for the node, and that would be very slow in most cases.
 »
•  » » its showing RTE . fix it
 » Hello!First of all, I would suggest you to write your own version of the code (for testing you have 20C — Dijkstra? problem here on Codeforces), because you will learn how the algorithm works and how to use it. However I will give you my code :). Keep in mind you can find more versions of Dijkstra on geekforgeeks, e-maxx, youtube, ...Here is my Dijkstra template: https://github.com/Sprdalo/Compete/blob/master/dijkstra.sublime-snippetTo see how to use it go to my submit for this problem which is given here.
 » Checked with C. Dijkstra?. #include using namespace std; #define debug(x) cout<<#x<<" is "< struct Dijkstra { int node,edge; vector< vector< pair > > adj; vector< T > level; vector parent; Dijkstra(int _node, int _edge) : node(_node), edge(_edge) { vector(node+1).swap(parent); vector(node+1, numeric_limits::max()).swap(level); vector< vector< pair > > (node+1).swap(adj); } void add_edge(int u, int v, T w) { adj[u].push_back({v,w}); adj[v].push_back({u,w}); } void traverse(int src) { level[src] = 0; set< pair > s {{0,src}}; parent[src] = -1; while(not s.empty()) { auto it = *s.begin(); int cur_node = it.y; T cur_level = it.x; s.erase(s.begin()); for(auto u : adj[cur_node]) { if(level[u.x] - u.y > cur_level) { level[u.x] = cur_level + u.y; parent[u.x] = cur_node; s.insert({level[u.x],u.x}); } } } } void print_path(int x) { if(level[x] == numeric_limits::max()) { cout<<"-1\n"; return; } if(x == -1){ return; } print_path(parent[x]); cout<>node>>edge; Dijkstra d(node,edge); while(edge--){ int x,y; ll w; cin>>x>>y>>w; d.add_edge(x,y,w); } d.traverse(1); d.print_path(node); return 0; } 
•  » » Suggest you to put the code into the spoilerDone 
 » https://github.com/okwedook/olymp/blob/master/Dijkstra.cppThis is an actually fast and memory efficient (and also veeery short) implementation. It uses a few template features I use, but you can look at template.cpp in the same repo.
•  » » Thanks for your solution, I dont know I can take the path like that. But can I ask this questionIf we only need to calculate the distance without taking the path. Is this the optimized code or we can still improve it ? My codevector dist; vector mark; void dijkstra(int s) { fill(dist.begin(), dist.end(), INF); fill(mark.begin(), mark.end(), false); priority_queue > pq; pq.push({dist[s] = 0, s}); while(!pq.empty()){ int u = pq.top().se; pq.pop(); if (!mark[u]) mark[u] = true; else continue; for (pi v : G[u]) if (dist[v.fi] > dist[u] + v.se) pq.push({dist[v.fi] = dist[u] + v.se, v.fi}); } } 
•  » » » Your code uses pairs to store the set. It does actually increase memory usage (I'm only storing the indices) and time usage (as you are also comparing pairs, while I do only one comparison), But you should test your code, it seems pretty neat.
•  » » » » What is "neat". Is it mean it is almost similar ?
•  » » » » » It's good in my opinion.
•  » » » » » » 5 months ago, # ^ | ← Rev. 3 →   How about prim algorithm. How do you implement without using heap of pair ? prim()vector dis; int prim() { fill(all(dis), +INF); int res = 0; priority_queue > S; S.push({dis = 0, 1}); while (!S.empty()) { pi u = S.top(); S.pop(); if (dis[u.se] != u.fi) continue; res += dis[u.se]; dis[u.se] = 0; for (pi v : G[u.se]) if (dis[v.fi] > v.se) S.push({dis[v.fi] = v.se, v.fi}); } return res; } 
•  » » » » » » » You can use the same idea as used in my Dijkstra imple. Just store the indices of unused vertices and compare them using a custom comparator.
•  » » » » » » » » Ok thanks for your method
•  » » Hi! Why are we making flag false in line 16? Can you please give an example of such a case.
•  » » » It's a bug:) Must be i.f instead of f.
 » 5 months ago, # | ← Rev. 3 →   Dijkstra - priority_queue implementation#include #include #include #include using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() typedef pair pi; typedef vector vi; typedef vector vb; typedef vector vpi; typedef vector vmi; typedef vector vmpi; const int INF = 1e9 + 19; const int LIM = 1e5 + 15; int n, m; vmpi G; vb mark; vi dist; void dijkstra(int s) { fill(all(dist), +INF); fill(all(mark), false); priority_queue > pq; pq.push({dist[s] = 0, s}); while (!pq.empty()) { int u = pq.top().se; pq.pop(); if (mark[u]) continue; else mark[u] = true; for(auto v : G[u]) { if (dist[v.fi] > dist[u] + v.se) { dist[v.fi] = dist[u] + v.se; pq.push({dist[v.fi], v.fi}); } } } } int main() { cin >> n >> m; G.resize(n + 1); mark.assign(n + 1, false); dist.resize(n + 1); for (int i = 0; i < m; ++i) { int u, v, c; cin >> u >> v >> c; G[u].pb({v, c}); } int s, t; cin >> s >> t; dijkstra(s); if (dist[t] == INF) cout << "There is no path from " << s << " to " << t; else cout << "Min distance(" << s << " -> " << t << ") = " << dist[t]; return 0; }  Dijkstra - Set implementation#include #include #include #include using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair typedef pair pi; typedef vector vi; typedef vector vb; typedef vector vpi; typedef vector vmi; typedef vector vmpi; const int INF = 1e9 + 19; const int LIM = 1e5 + 15; int n, m; vmpi G; vb mark; vi dist; void dijkstra(int s){ fill(dist.begin(),dist.end(), LIM); set S; S.insert({dist[s] = 0, s}); while(!S.empty()){ int u = S.begin() -> se; S.erase(S.begin()); for(auto v : G[u]) { if(dist[v.fi] > dist[u] + v.se) { S.erase({dist[v.fi], v.fi}); dist[v.fi] = dist[u] + v.se; S.insert({dist[v.fi], v.fi}); } } } } int main() { cin >> n >> m; G.resize(n + 1); mark.assign(n + 1, false); dist.resize(n + 1); for (int i = 0; i < m; ++i) { int u, s, c; cin >> u >> s >> c; G[u].pb({s, c}); } int s, t; cin >> s >> t; dijkstra(s); if (dist[t] == INF) cout << "There is no path from " << s << " to " << t; else cout << "Min distance(" << s << " -> " << t << ") = " << dist[t]; return 0; }  SPFA - Queue implementation#include #include #include using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair typedef pair pi; typedef vector vi; typedef vector vb; typedef vector vmi; typedef vector vpi; typedef vector vmpi; const int INF = 1e9 + 19; int n, m; vmpi G; vb mark; vi dist; void spfa(int s) { fill(dist.begin(), dist.end(), INF); fill(mark.begin(), mark.end(), false); mark[s] = true; dist[s] = 0; deque S(1, s); while (!S.empty()) { int u = S.front(); S.pop_front(); mark[u] = false; for (int i = 0; i < G[u].size(); ++i) { int v = G[u][i].fi; int w = G[u][i].se; if (dist[v] > dist[u] + w) dist[v] = dist[u] + w; if (!mark[v]) { S.push_back(v); mark[v] = true; } } } } int main() { cin >> n >> m; G.resize(n + 1); mark.assign(n + 1, false); dist.resize(n + 1); for (int i = 0; i < m; ++i) { int u, v, c; cin >> u >> v >> c; G[u].pb({v, c}); } int s, t; cin >> s >> t; spfa(s); if (dist[t] == INF) cout << "There is no path from " << s << " to " << t; else cout << "Min distance(" << s << " -> " << t << ") = " << dist[t]; return 0; } 
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   SPyofgame In your priority queue implementation , priority_queue pq , In this line why you use less ? Maybe we should use greater. Isn't ?
•  » » » Yup, it should be greater, thanks for reminding me. For some reasons I push wrong code :'(
 » 2 months ago, # | ← Rev. 2 →   #include #define ll long long #define pb push_back #define f first #define s second #define mp make_pair #define inf 999999999999 using namespace std; ll n,m; ll dist,par; void dij(vector > graph[]) { ll i; set < pair > s; s.insert(mp(0,1)); for(i=1;i<=n;i++) { dist[i]=inf; } dist=0; par=0; while(!s.empty()) { set > :: iterator itr; itr=s.begin(); ll u=itr->s; s.erase(s.begin()); for(i=0;idist[u]+wn) { if(dist[v]!=inf) { s.erase(s.find(mp(dist[v],v))); } dist[v]=dist[u]+wn; s.insert(mp(dist[v],v)); par[v]=u; } } } } main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; ll i; vector > graph[n+1]; for(i=1;i<=m;i++) { ll a,b,w; cin>>a>>b>>w; graph[a].pb(mp(w,b)); graph[b].pb(mp(w,a)); } dij(graph); if(dist[n]==inf) cout<<"-1"; else { vector v; i=n; v.pb(i); while(i!=1) { v.pb(par[i]); i=par[i]; } for(i=v.size()-1;i>=0;i--) cout<
 » 2 months ago, # | ← Rev. 4 →   Dijkstra's (CP-Algorithms) Take a look at the priority queue based implementation. You could probably modify it a bit to make it shorter to code. Dijkstra's With Path Printing
 » I use this implementation. It is from this book. for (int i = 1; i <= n; i++) distance[i] = INF; distance[x] = 0; q.push({0,x}); while (!q.empty()) { int a = q.top().second; q.pop(); if (processed[a]) continue; processed[a] = true; for (auto u : adj[a]) { int b = u.first, w = u.second; if (distance[a]+w < distance[b]) { distance[b] = distance[a]+w; q.push({-distance[b],b}); } } } 
•  » » Can you please tell me how can you modify it for Prim's Algorithm?
 » cf rating doesnt matter
»
 » #include using namespace std; void addEdge(vector> adj[], int u, int v, int w) { adj[u].push_back(make_pair(v, w)); adj[v].push_back(make_pair(u, w)); } void Dijkstra(vector> G[], int n, int source) { priority_queue> pq; // int dist[n]; for(int i=0; i dist[v] + weight) { dist[G[v][x].first] = dist[v] + weight; pq.push(make_pair(dist[v] + weight, G[v][x].first)); } } } printf("Vertex Distance from Source\n"); for (int i = 0; i < n; ++i) printf("%d \t\t %d\n", i, dist[i]); } int main() { int V = 9; vector> g; addEdge(g, 0, 1, 4); addEdge(g, 0, 7, 8); addEdge(g, 1, 2, 8); addEdge(g, 1, 7, 11); addEdge(g, 2, 3, 7); addEdge(g, 2, 8, 2); addEdge(g, 2, 5, 4); addEdge(g, 3, 4, 9); addEdge(g, 3, 5, 14); addEdge(g, 4, 5, 10); addEdge(g, 5, 6, 2); addEdge(g, 6, 7, 1); addEdge(g, 6, 8, 6); addEdge(g, 7, 8, 7); Dijkstra(g,9,0); return 0; }