electro177's blog

retracing path in dijstra

By electro177, history, 3 years ago, In English 
#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define ar array
 
const int mxa = 1e5 + 1;
ll a, b, c, n, m;
vector <ar<ll, 2>> adj[mxa];
ll dist[mxa];
 
 
 
int main() {
 
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> a >> b >> c; --a, --b;
    adj[a].push_back({c, b});
 
  }
 
  memset(dist, 0x3f, sizeof(dist));
 
  priority_queue< ar<ll, 2>  , vector<ar<ll, 2>>, greater<ar<ll, 2>> > pq;
  dist[0] = 0;
  pq.push({0, 0});
  while (pq.size()) {
 
    ar<ll, 2> node = pq.top();
    pq.pop();
 
    if (node[0] > dist[node[1]])continue;
 
    for ( ar<ll, 2> child : adj[node[1]]) {
 
      if (dist[child[1]] > node[0] + child[0]) {
        dist[child[1]] = node[0] + child[0];
        pq.push({dist[child[1]], child[1]});
      }
    }
 
  }
 
  for (int i = 0; i < n; i++) cout << dist[i] << " ";
 
}

I have implemented code for Dijstra ,but it finds only min distance of each node from source node. could anyone please help how to retace the shortest path in this approach .Thank you

  • Vote: I like it
  • -21
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

https://codeforces.com/contest/20/problem/C I believe this is the problem you mentioned in the blog so I guess checking AC codes will help

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If the shortest path to node v goes through node u, then mark it, and you’ll end up with a shortest path tree.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Use a parent array p, where p[i]=parent of the ith node. For a path from u to v, put p[u]=-1 and while you update the distance you also update the parent of that node. At the end you just traverse the parent array from v to u and store the path and print in reverse order.

Sample code
→ Reply