5 - 多源最短路
快速入门图论!本文介绍图论中的“多源最短路”问题,以及解决它的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