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

• +1

 » 5 years ago, # |   0
 » 5 years ago, # |   0 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.
 » 5 years ago, # |   0 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)
•  » » 2 months ago, # ^ |   -8 why you use if(dis>d[u]) continue?
•  » » » 2 months ago, # ^ |   0 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.
 » 5 years ago, # |   0
•  » » 22 months ago, # ^ |   -24 its showing RTE . fix it
 » 22 months ago, # |   0 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.
 » 11 months ago, # |   -8 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; } 
•  » » 2 months ago, # ^ |   0 Suggest you to put the code into the spoilerDone 
 » 2 months ago, # |   0 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.
•  » » 2 months ago, # ^ |   0 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}); } } 
•  » » » 2 months ago, # ^ |   +1 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.
•  » » » » 2 months ago, # ^ |   0 What is "neat". Is it mean it is almost similar ?
•  » » » » » 2 months ago, # ^ |   +1 It's good in my opinion.
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 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[1] = 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 e : G[u]) if (dis[v.fi] > v.se) S.push({dis[v.fi] = v.se, v.fi}); } return res; } 
•  » » » » » » » 2 months ago, # ^ |   +1 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.
•  » » » » » » » » 2 months ago, # ^ |   0 Ok thanks for your method
 » 2 months ago, # | ← Rev. 3 →   0 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; }