dimanche 19 mai 2019

Dijkstra Algorithm Gives Infinite Loop

I am new to shortest-paths algorithms and am working on implementing Dijkstra's Algorithm. In my implementation, which utilizes a priority queue, I am getting an infinite loop. I cannot identify the cause of this problem. Can anybody see what is causing it? Sample input:

5 10 1

1 2 5

2 3 2

3 4 6

4 3 4

5 4 1

1 5 10

2 4 9

3 1 7

2 5 3

5 2 2

CODE BELOW:

#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
typedef long long LL;
#define pii pair<int, int>
#define pLL pair<LL, LL>
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define INF 1<<29

vector<vector<pLL> > a;
LL dist[100];

void relax(LL u, LL v, LL w) {
  dist[v] = min(dist[v], dist[u] + w);
}

int main() {
  dist[1] = 0;
  a.resize(100);
  //ofstream fout("test.out");
  //ifstream fin("test.in");
  int v, e, s; cin >> v >> e >> s;
  for (int i = 2; i <= v; i++) dist[i] = INF;
  for (int i = 0; i < e; i++) {
    LL x, y, w; cin >> x >> y >> w;
    a[x].pb(mp(y, w));
  }
  priority_queue<pLL, vector<pLL>, greater<pLL> > pq;
  // .first = dist, .second = vertex
  for (int i = 2; i <= v; i++) pq.push(mp(INF, i));
  pq.push(mp(0, 1));
  while (!pq.empty()) {
    pLL u = pq.top();
    pq.pop();
    for (pLL p : a[u.s]) {
      relax(u.s, p.f, p.s);
      pq.push(mp(dist[p.f], p.f));
    }
  }
  for (int i = 1; i <= v; i++) {
    cout << i << ": " << dist[i] << "\n";
  }
  return 0;
}

Aucun commentaire:

Enregistrer un commentaire