floyd（弗洛伊德算法）

xiufanivan · 2023-03-31 16:36:30 · 个人记录

路径图：

graph TD
    0((0)) --10--> 2((2)) --5--> 1((1))
    0((0)) --30--> 4((4)) --20--> 3((3)) --10--> 5((5))
    2((2)) --50--> 3((3))
    0((0)) --100--> 5((5))
    4((4)) --60--> 5((5))

邻接矩阵：

输出结果： 行数 i 到列数 j 的最短路径

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 205;
const int INF = 0x3f3f3f3f;

int dis[N][N];

void floyd() {
    for (int k = 0; k <= 5; k++)
        for (int i = 0; i <= 5; i++)
            for (int j = 0; j <= 5; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}

int main() {
    // 输入数组 
    for (int i = 0; i <= 5; i++) {
        for (int j = 0; j <= 5; j++) {
            dis[i][j] = INF;
        }
    }
    for (int i = 0; i <= 5; i++) {
        dis[i][i] = 0;
    }
    dis[0][2] = 10;
    dis[0][4] = 30;
    dis[0][5] = 100;
    dis[2][1] = 5;
    dis[2][3] = 50;
    dis[3][5] = 10;
    dis[4][3] = 20;
    dis[4][5] = 60;
    // 输出数组 
    for (int i = 0; i <= 5; i++) {
        for (int j = 0; j <= 5; j++) {
            if (dis[i][j] == INF) cout << "INF" << "\t";
            else cout << dis[i][j] << "\t";
        }
        cout << endl;
    }
    cout << "============================================" << endl;
    // 更新最短路径 
    floyd();
    // 输出最终结果 
    for (int i = 0; i <= 5; i++) {
        for (int j = 0; j <= 5; j++) {
            if (dis[i][j] == INF) cout << "INF" << "\t";
            else cout << dis[i][j] << "\t";
        }
        cout << endl;
    }
    return 0;
}