floyd.cpp
Thuật toán Floyd - Warshall
Mục đích : tìm đường đi ngắn nhất giữa mọi cặp điểm.
Độ phức tạp: O(|V|^3) hay O(n^3)
Floyd.cpp
#include <stdio.h>
const int oo = 1000111000;
int a[239][239];
int n, m;
void minimize(int &a, int b) {
if (a > b)
a = b;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j] = oo;
for (int i = 1; i <= n; i++)
a[i][i] = 0;
for (int i = 1; i <= m; i++) {
int p, q, w;
scanf("%d%d%d", &p, &q, &w);
a[p][q] = a[q][p] = w;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
minimize(a[i][j], a[i][k] + a[k][j]);
printf("%d\n", a[1][n]);
}
Sample Input
3 3
1 2 50
2 3 60
1 3 600
Sample Output
110
Nhận xét
Vì Floyd có độ phức tạp n^3 nên ta chỉ áp dụng cho các bài toán có số đỉnh nhỏ hơn hoặc bằng 400.
Tốt hơn hết là sử dụng ma trận kề cho thuật toán này.
Có thể dùng cho đồ thị có hướng, bạn có thể thay lệnh a[p][q] = a[q][p] = w bằng a[p][q]= w.
Sau khi chạy thuật toán, a[i][j] sẽ là đường đi ngắn nhất từ i đến j với i, j từ 1 đến n.