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