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.