最简单的最短路径算法 - Floyd_Warshall算法

算法

---

参考《啊哈算法》第六章第一节，PDF在线阅读

介绍

详细介绍请看PDF，个人理解，这是一个暴力+动态规划的思想，在二维数组中每次都从第1，2，3 ... N节点中转一次，如果可以中转且路径较小，那么我们就更新存储路径的二维数组。

这个算法可以解决多源最短路径问题

时间复杂度 O(N^3)

代码

/**
 * 多源最短路径
 * Floyd_Warshall算法
 * 时间复杂度 O(N^3)
 */

#include <iostream>
#include <climits>

using namespace std;

int n;

void print(int e[10][10]) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%15d", e[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

int main() {
    int e[10][10] = {0}, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = INT_MAX;
    int a, b, c;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> c;
        e[a][b] = c;
    }

    for (int k = 1; k <= n; k++) { //让二维数组依次从k点中转一下
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                //可以中转取较小值，无法到达就跳过
                if (e[i][j] > e[i][k] + e[k][j] && e[i][k] != INT_MAX && e[k][j] != INT_MAX)
                    e[i][j] = e[i][k] + e[k][j];
            }
//        print(e);
    }

    print(e);

    return 0;
}

/**
5 8
1 3 2
1 5 4
2 5 2
3 4 3
4 2 5
5 2 5
5 3 3
5 4 1
              0              9              2              5              4
     2147483647              0              5              3              2
     2147483647              8              0              3             10
     2147483647              5             10              0              7
     2147483647              5              3              1              0

4 8
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12
         0         2         5         4
         9         0         3         4
         6         8         0         1
         5         7        10         0
 */