dijkstra.cpp
Dijkstra - Tìm đường đi ngắn nhất trên đồ thị
Mục đích : Từ một đỉnh S, ta muốn biết độ dài đường đi ngắn nhất từ S đến tất cả các đỉnh còn lại (trong đồ thị có hướng hoặc vô hướng)
Độ phức tạp : O (n log n)
dijkstra.cpp
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
const int oo = 1000111000;
typedef pair<int, int> ii;
vector<ii> a[2309];
int n, m;
int d[2309];
void dijkstra() {
priority_queue<ii, vector<ii>, greater<ii>> pq;
for (int i = 1; i <= n; i++)
d[i] = oo;
d[1] = 0;
pq.push(ii(0, 1));
while (pq.size()) {
int u = pq.top().second;
int du = pq.top().first;
pq.pop();
if (du != d[u])
continue;
for (int i = 0; i < a[u].size(); i++) {
int v = a[u][i].second;
int uv = a[u][i].first;
if (d[v] > du + uv) {
d[v] = du + uv;
pq.push(ii(d[v], v));
}
}
}
}
int main() {
int p, q, m, w;
scanf("%d%d", &n, &m);
while (m--) {
scanf("%d%d%d", &p, &q, &w);
a[p].push_back(ii(w, q));
a[q].push_back(ii(w, p));
}
dijkstra();
for (int i = 1; i <= n; i++)
printf("d( 1 -> %d ) = %d\n", i, d[i]);
}
Sample Input
5 5
1 2 10
1 3 10
2 4 20
3 4 25
1 4 33
Sample Output
d( 1->1 ) = 0
d( 1->2 ) = 10
d( 1->3 ) = 10
d( 1->4 ) = 30
d( 1->5 ) = 1000111000