Floyd算法|Floyd算法 解决多元汇最短路问题
接下来是图论问题求解最短路问题的最后一个，求解多元汇最短路问题
我们之前一般都是问1-n的最短路径，这里我们要能随便去问i到j的最短路径：
这里介绍一下Floyd算法：我们只有一个d[maxn][maxn]数组直接存储从i到j的最短路径，我们先看代码：
#include
#define maxn 210
#define INF 1000000000
using namespace std;
int d[maxn][maxn],n,m,q;
void floyd()
{
for(int k = 1;
k<=n;
k++)
for(int i = 1;
i<=n;
i++)
for(int j = 1;
j<=n;
j++)
d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
cin >> n >> m >> q;
for(int i = 1;
i<=n;
i++)
for(int j = 1;
j<=n;
j++)
if(i==j) d[i][j] = 0;
else d[i][j] = INF;
while(m--){
int x,y,z;
cin >> x >> y >> z;
d[x][y] = min(d[x][y],z);
}
floyd();
while(q--){
int x,y;
cin >> x >> y;
if(d[x][y] > INF/2) cout << "impossible" << '\n';
else cout << d[x][y] << '\n';
}
return 0;
}
分析：·首先，我们可以看到我们先对d数组进行初始化，使自环为0，其他取INF；
·然后我们读入每条边的数值，我们就要取最小值。是两条直接相连边的边权值最小；
·最后我们直接套三重循环，如下理解：
【Floyd算法|Floyd算法 解决多元汇最短路问题】f[i, j, k]表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离。那么f[i, j, k] = min(f[i, j, k - 1), f[i, k, k - 1] + f[k, j, k - 1]。
因此在计算第k层的f[i, j]的时候必须先将第k - 1层的所有状态计算出来，所以需要把k放在最外层
推荐阅读
- 一文搞懂|一文搞懂 SLAM 中的Extension Kalman Filter 算法编程
- springboot|springboot html调用js无效400问题及解决
- Spring|Spring @Cacheable注解类内部调用失效的解决方案
- 车企销量怎么“加速冲”（Smartbi制造业解决方案告诉你！）
- Springboot从配置文件properties读取字符串乱码的解决
- 计算机视觉算法工程师|算法工程师15——数据结构与算法加强版
- 算法|【算法】时间复杂度真的不“复杂”
- 数据结构|数据结构与算法—— 树
- 数据结构和算法基于python语言_数据结构与算法（Python语言描述）
- Python系列|数据结构与算法笔记（五）——队列(FIFO队列、双端队列)