c++中如何实现Floyd最短路径_c++ Floyd最短路径实现方法

#include <iostream>

#include <vector>

#include <climits>

using namespace std;

const int INF = INT_MAX / 2; // 防止加法溢出

void floyd(vector<vector<int>>& dist, int n) {

    for (int k = 0; k

        for (int i = 0; i

            for (int j = 0; j

                if (dist[i][k] != INF && dist[k][j] != INF) {

                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

                }

            }

        }

    }

}

void printDist(const vector<vector<int>>& dist, int n) {

    cout

    for (int i = 0; i

        for (int j = 0; j

            if (dist[i][j] == INF)

                cout << "INF ";

Eva Design System

基于深度学习的色彩生成器

86

查看详情

            else

                cout << dist[i][j] << " ";

        }

        cout << endl;

    }

}

int main() {

    int n = 4; // 节点数

    vector<vector<int>> dist(n, vector<int>(n, INF));

    // 自身到自身距离为0

    for (int i = 0; i

        dist[i][i] = 0;

    // 添加边：u -> v, 权重 w

    dist[0][1] = 3;

    dist[0][2] = 6;

    dist[1][2] = 4;

    dist[1][3] = 4;

    dist[2][3] = 8;

    floyd(dist, n);

    printDist(dist, n);

    return 0;

}