Fshl0

Dijkestra Function

Sep 21st, 2021
488
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void Dijkestra (int sourceNode) {
  2.     priority_queue <pair <ll, int>, vector<pair <ll, int> >, greater<pair <ll, int> > > pq;
  3.    
  4.     for (int i = 1; i < j; i++)
  5.         dist[i] = INF;
  6.     dist[sourceNode] = 0;
  7.    
  8.     pq.push ({0, sourceNode});
  9.     while (!pq.empty()) {
  10.         pair <ll, int> v = pq.top();
  11.         pq.pop ();
  12.        
  13.         if (v.F != dist[v.S])
  14.             continue;
  15.        
  16.         for (auto edge: adj[v.S]) {
  17.             int to = edge.F, len = edge.S;
  18.             if (dist[v.S] + len < dist[to]) {
  19.                 dist[to] = dist[v.S] + len;
  20.                 //pa[to] = v.S;
  21.                 pq.push ({dist[to], to});
  22.             }
  23.         }
  24.     }
  25.    
  26.     return;
  27. }
RAW Paste Data