Floyd-Warshall算法

说实话，在一开始没学的时候还觉得挺高大上的算法，学了之后发现，最短路四大算法，这是最暴力的一个。。

Floyd-Warshall算法，一般也叫Floyd算法，这个算法正如网传的那样：核心算法只有5行：

for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= n; k++) if(dis[j][k] > dis[j][i] + dia[i][k])
 dis[j][k] = dis[j][i] + dia[i][k];

(话说光是看那三个for就觉得有够暴力了阿喂。。。。。

该算法基本思想只有一个：如果从一个点到另一个点的直接路径不是最短的，那最短路肯定要经过第三个点。所以就用所有的点都当一次中间点，来判断是不是任意两点之间经过中间点路程会减小。

示例代码：

typedef long long LL;
const int MAXN = 100;
const int INF = 0x3f3f3f3f;
using namespace std;

int pre[MAXN + 3][MAXN + 3], dist[MAXN + 3][MAXN + 3]; //pre 储存路径; dist 存储最短距离
void floyd(int n, int gra[][MAXN + 3]) {
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) dist[i][j] = gra[i][j], pre[i][j] = j;  //初始化
    for(int k = 1; k <= n; k++) {   //尝试经过 k 个点对每对顶点之间的距离进行更新
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    pre[i][j] = pre[i][k];
                }
            }
        }
    }
}

int pfpath(int u, int v) { //打印最短路径
    while(u != v) {
        cout << u  << " ";
        u = pre[u][v];
    }
    cout << u << endl;
}

int gra[MAXN + 3][MAXN + 3];
int main() {
    int n, m;
    while(cin >> n >> m){ // n 个点, m 条边
        for(int i = 0; i <= n; i++) for(int j = -1; j <= n; j++){
            gra[i][j] = (i == j ? 0 : INF);
        }
        for(int i = 0; i < m; i++) {
            int u, v, w; cin >> u >> v >> w;
            gra[u][v] = gra[v][u] = w;  //无向图
        }
        floyd(n, gra);
    }
    return 0;
}