专业制作教学课件_互联网营销师题库及答案_seo排名优化厂家_热门职业培训班

Floyd求最短路 题解

题目传送门

854. Floyd求最短路

一、题目描述

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出"impossible"。数据保证图中不存在负权回路。

二、题目分析

1. 这是一个典型的多源最短路径问题，需要处理多个点对之间的最短路径查询
2. 图中可能存在负权边，但没有负权回路（保证有解）
3. 需要高效处理大量查询（最多n²次查询）

三、解题思路

使用Floyd算法来解决多源最短路径问题：

1. 初始化距离矩阵，对角线为0，其他为无穷大
2. 读入边信息，保留最短的边（处理重边）
3. 执行Floyd算法三重循环更新所有点对的最短距离
4. 处理查询时直接查表输出结果

四、算法讲解

Floyd算法

原理：动态规划思想，逐步考虑通过中间节点来松弛所有点对的距离

使用场景：

• 稠密图的多源最短路径
• 可以处理负权边（但不能有负权回路）
• 适合小规模图（n≤200）

实现步骤：

1. 初始化距离矩阵dist[i][j]表示i到j的直接距离
2. 三重循环：
   • 外层循环k：中间节点
   • 内层双重循环i,j：尝试用k松弛i到j的距离
3. 最终dist[i][j]存储的就是i到j的最短距离

例子：
对于样例输入：

3 3 2
1 2 1
2 3 2
1 3 1

• 初始距离矩阵：dist[1][2]=1, dist[2][3]=2, dist[1][3]=1
• Floyd执行后：距离矩阵不变（已经是最短）
• 查询2→1：不存在路径（输出impossible）
• 查询1→3：直接有边长为1的路径

五、代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;const int N = 210, INF = 1e9;  // 定义最大点数和无穷大值
int dist[N][N];  // 距离矩阵，存储所有点对的最短距离
int n, m, k;     // n点数，m边数，k查询数void floyd() {// Floyd算法核心：三重循环动态更新最短距离for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}int main() {cin >> n >> m >> k;// 初始化距离矩阵for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) {if (i == j) dist[i][j] = 0;  // 自己到自己的距离为0else dist[i][j] = INF;       // 初始时设为无穷大}// 读入边信息for (int i = 1; i <= m; i++) {int x, y, z;cin >> x >> y >> z;dist[x][y] = min(dist[x][y], z);  // 处理重边，保留最短的}floyd();  // 执行Floyd算法// 处理查询while (k--) {int x, y;cin >> x >> y;// 注意判断条件：由于有负权边，可能略微小于INFif (dist[x][y] > INF / 2) cout << "impossible" << endl;else cout << dist[x][y] << endl;}return 0;
}

六、重点细节

1. 初始化：对角线初始化为0，其他为无穷大
2. 重边处理：保留最短的边
3. 无穷大判断：由于负权边的存在，不能直接判断等于INF
4. 空间优化：Floyd算法可以原地操作，不需要额外空间

七、复杂度分析

• 时间复杂度：O(n³) - Floyd三重循环
• 空间复杂度：O(n²) - 存储距离矩阵

对于本题n≤200，n³=8,000,000，在可接受范围内。

八、总结

Floyd算法是解决多源最短路径问题的经典算法，虽然时间复杂度较高，但对于小规模图非常适用。其优势在于实现简单，能处理负权边，并且可以一次性求出所有点对的最短距离，适合查询密集的场景。