簡介

Floyd算法的作用是求出一個圖之間任意兩點(diǎn)的最短距離，被認(rèn)為是一個經(jīng)典的動態(tài)規(guī)劃算法——然而我至今仍然沒搞明白動態(tài)規(guī)劃到底是什么意思2333……

原理

從任意節(jié)點(diǎn)i到任意節(jié)點(diǎn)j的最短路徑不外乎2種可能——要么是直接從i到j(luò)，要么是從i經(jīng)過若干個節(jié)點(diǎn)k到j(luò)。

所以，我們假設(shè)Dis(i,j)為節(jié)點(diǎn)u到節(jié)點(diǎn)v的最短路徑的距離（這里用鄰接矩陣表示圖）：

對于每一個節(jié)點(diǎn)k，我們檢查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立——證明從i到k再到j(luò)的路徑比i直接到j(luò)的路徑短，我們便設(shè)置Dis(i,j) = Dis(i,k) + Dis(k,j)，這樣一來，當(dāng)我們遍歷完所有節(jié)點(diǎn)k，Dis(i,j)中記錄的便是i到j(luò)的最短路徑的距離。

一個實(shí)例

https://pta.patest.cn/pta/test/558/exam/4/question/9929

代碼

#include <iostream>
#include <cstring>
#include <vector>
#define INF 65536
using namespace std;
class Graph {
private:
    int n;
    vector<vector<int>> matrix;
public:
    Graph(int N) {
        n = N;
        vector<vector<int>>_matrix(n, vector<int>(n, INF));
        matrix = _matrix;
    }
    ~Graph() {
        
    }
    void build(int m) {
        int a, b, weight;
        for (int i = 0; i < m; i++)
        {
            cin >> a >> b >> weight;
            matrix[a - 1][b - 1] = weight;
            matrix[b - 1][a - 1] = weight;
            //注意數(shù)組下標(biāo)從0開始計數(shù)
        }
    }
    void Floyd() {//Floyd算法
        for (int k= 0;k <n; k++)
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (matrix[i][k]+matrix[k][j]<matrix[i][j])
                    {
                        matrix[i][j] = matrix[i][k] + matrix[k][j];
                        //path[i][j]=k; 如有需要可以記錄路徑
                    }
                }
            }
        }
    }
    int findMaxDist(int vertex) {  //找到頂點(diǎn)vertex到其他頂點(diǎn)最長的路徑
        int maxDist = 0;
        for (int i = 0; i < n; i++)
        {
            if (i!=vertex&&matrix[vertex][i]>maxDist) {//注意不要計算自己到自己的距離
                maxDist = matrix[vertex][i];
            }
        }
        return maxDist;
    }
};
int main()
{
    int N, M;
    cin >> N >> M;
    Graph graph(N);
    graph.build(M);
    graph.Floyd();
    int animal = 0;
    int miniDist = INF;
    int check = graph.findMaxDist(3);
    for (int i = 0; i < N; i++)
    {
        auto dist = graph.findMaxDist(i);
        //類型自動推導(dǎo)fromCpp_11，我也來裝個逼23333
        if (dist>=INF)
        {
            cout << 0 << endl;
            return 0;
            //自動退出？非連通集？
        }
        if (miniDist>dist) //如果當(dāng)前找到的距離最小則更新miniDist
        {
            animal = i + 1;//還是從0開始的問題
            miniDist = dist;
        }
    }
    cout << animal << " " << miniDist << endl;
    return 0;
}