快速入门图论！本文介绍图论中的“多源最短路”问题，以及解决它的Floyd算法，时间复杂度。

多源最短路问题

就是起点终点不唯一，求它俩之间的最短路。

Floyd算法

推导过程详见灵神题解。这里直接给出代码模板：

// 使用邻接矩阵g[N][N]存储图
// 如果不用g的话, 可以直接用g存储最短距离
dist[N][N] <- g[N][N];
// Floyd
for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            dist[i][j] <- min(dist[i][j], dist[i][k] + dist[k][j]);

练习题

854. Floyd求最短路 - AcWing题库

Floyd算法模板题：

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main()
{
    int n, m, q;
    cin >> n >> m >> q;

    // 建图
    int maxVal = numeric_limits<int>::max() / 2;
    vector<vector<int>> g(n + 5, vector<int>(n + 5, maxVal / 2));
    for (int i = 0; i < n + 5; ++i)
        for (int j = 0; j < n + 5; ++j)
            if (i == j)
                g[i][j] = 0;
    for (int i = 0; i < m; ++i)
    {
        int a, b, w;
        cin >> a >> b >> w;
        g[a][b] = min(g[a][b], w);
    }

    // Floyd算法(节点1起点)
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

    // 回答询问
    for (int i = 0; i < q; ++i)
    {
        int a, b;
        cin >> a >> b;
        // 这里 /2, /4 看情况, 推荐/4
        if (g[a][b] >= maxVal / 4)
            cout << "impossible" << '\n';
        else
            cout << g[a][b] << '\n';
    }

    return 0;
}

2642. 设计可以求最短路径的图类 - 力扣（LeetCode）

这道题也是Floyd模板题，难点在于对addEdge的处理，其实没必要每addEdge一次，重算Floyd一次，这也太耗时了。可以看情况更新最短距，例如添加边之前是i -g[i][j]-> j，添加边之后是i -g[i][a]-> a -w-> b -g[b][j]-> j，当w < g[i][j]时，才有必要更新最短矩。

参考代码如下：

class Graph {
private:
    vector<vector<int>> g;

public:
    Graph(int n, vector<vector<int>>& edges)
        : g(n, vector<int>(n, numeric_limits<int>::max() / 4))  // 防止结案发溢出
        {
            // 建图
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    if (i == j)
                        g[i][j] = 0;
            for (auto& edge : edges)
            {
                int a = edge[0], b = edge[1], w = edge[2];
                g[a][b] = min(g[a][b], w); 
            }

            // Floyd
            for (int k = 0; k < n; ++k)
                for (int i = 0; i < n; ++i)
                    for (int j = 0; j < n; ++j)
                        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
        }

    void addEdge(vector<int> edge) {
        int a = edge[0], b = edge[1], w = edge[2];
        // 从:   i ---g[i][j]---> j
        // 变成: i -g[i][a]-> a -w-> b -g[b][j]-> j
        // 如果g[i][j] <= w, 就没必要更新最短矩
        if (g[a][b] <= w)
            return;
        // 否则就要更新最短矩
        for (int i = 0; i < g.size(); ++i)
            for (int j = 0; j < g.size(); ++j)
                g[i][j] = min(g[i][j], g[i][a] + w + g[b][j]);

    }

    int shortestPath(int node1, int node2) {
        int ans = g[node1][node2];
        return ans >= numeric_limits<int>::max() / 4 ? -1 : ans;
    }
};

使用Floyd算法，适用于shortestPath询问次数多的场景；如果addPath较多，还是推荐用Dijkstra算法。

1334. 阈值距离内邻居最少的城市 - 力扣（LeetCode）

本题需要频繁询问城市a，b的最短距离，适合先用Floyd算法计算出各个城市间最短的距离后，再询问。

参考代码如下：

int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
    vector<vector<int>> g(n, vector<int>(n, numeric_limits<int>::max() / 4));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (i == j)
                g[i][j] = 0;
    for (auto& edge : edges)
    {
        int a = edge[0], b = edge[1], w = edge[2];
        g[b][a] = g[a][b] = min(g[a][b], w);
    }

    // Floyd
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

    int ans = 0;
    int minCity = n + 1;
    for (int i = 0; i < n; ++i)
    {
        int cnt = 0;
        for (int j = 0; j < n; ++j)
        {
            if (g[i][j] <= distanceThreshold)
                ++cnt;
        }
        if (cnt <= minCity)
        {
            minCity = cnt;
            ans = i;
        }
    }
    return ans;
}

1334. 阈值距离内邻居最少的城市 1855
2976. 转换字符串的最小成本 I 1882
2959. 关闭分部的可行集合数目 2077
2977. 转换字符串的最小成本 II 2696