Floyd
最简单的最短路径算法,计算任意两点的最短路径,适用于负边权。通过
O(n^3)
的时间复杂度找到最短路径
代码模板
dis[u][v]
表示从u
到v
的最短路径长度。初始化:点u
、v
如果有边连接,则dis[u][v]=w[u][v]
。如果不相连则dis[u][v]=INF
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dis[i][j] > dis[i][k] + dis[k][j])
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
dis[i][j]
得出的就是从i
到j
的最短距离。
思想
三层循环,第一层循环中间点k
,第二、三层循环起点和终点i
、j
,如果点i
到点k
的距离加上点k
到点j
的距离小于原先点i
到点j
的距离,那么就做更新。
值得注意
- 如果将
dis[][]
初始化为INT_MAX
,那么在循环中计算距离时可能产生溢出。建议初始化为0x3f3f3f3f
,因为0x3f3f3f3f + 0x3f3f3f3f
并不会超出INT_MAX
,memset(,0x3f,sizeof())。 -
if
语句可加入i^j && i^k && j^k
的判断,因为在初始化时,到自身的距离因为0
,可直接跳过。
例题
洛谷P1364 医院设置
代码如下
#include <bits/stdc++.h>
using namespace std;
int n, w[101], u, v, dis[101][101];
int main() {
memset(dis, 0x3f, sizeof dis);
cin >> n;
for (int i = 1; i <= n; i++) {
dis[i][i] = 0;
cin >> w[i] >> u >> v;
dis[i][u] = dis[u][i] = 1;
dis[i][v] = dis[v][i] = 1;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i^j&&i^k&&j^k && dis[i][j] > dis[i][k] + dis[k][j])
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
int res = 0x7f7f7f7f;
for (int i = 1; i <= n; i++) {
int temp = 0;
for (int j = 1; j <= n; j++) {
temp += w[j] * dis[i][j];
}
res = min(res, temp);
}
printf("%d\n", res);
return 0;
}