AcWing854. Floyd求最短路

2024-08-27 23:52

文章标签 短路 floyd acwing854

本文主要是介绍AcWing854. Floyd求最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

注意：Floyd是求图里面任意两个点x，y之间的最短距离

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 210, INF = 1e9;int n, m, Q;
int d[N][N];void floyd()
{
//枚举1~k个中间节点，尝试通过这几个点中转来达到更短距离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()
{scanf("%d%d%d", &n, &m, &Q);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )if (i == j) d[i][j] = 0;//自己到自己是0距离else d[i][j] = INF;//while (m -- ){int a, b, c;scanf("%d%d%d", &a, &b, &c);//min是因为处理重边，c是权重d[a][b] = min(d[a][b], c);}floyd();while (Q -- ){int a, b;scanf("%d%d", &a, &b);int t = d[a][b];//如果存在负权环，会走该分支，会一直减小总路径//或者真的是不可达也会走该分支if (t > INF / 2) puts("impossible");//可达的情况else printf("%d\n", t);}return 0;
}

扩展内容：

迪杰斯特拉和弗洛伊德算法区别：

迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd-Warshall）算法都是图论中用于求解最短路径问题的著名算法，但它们在设计、应用场景和效率上有所不同：

算法设计：
- 迪杰斯特拉算法：是一种贪心算法，用于在加权图中找到单个源点到所有其他顶点的最短路径。它适用于没有负权边的图。
- 弗洛伊德算法：是一种动态规划算法，用于在加权图中找到所有顶点对之间的最短路径。它可以处理包含负权边的图，但不能处理负权环。
应用场景：
- 迪杰斯特拉算法：适用于单源最短路径问题，例如从某个城市到其他所有城市的最短路线。
- 弗洛伊德算法：适用于全局最短路径问题，例如在所有城市之间找到最短的路线。
效率：
- 迪杰斯特拉算法：时间复杂度为 $O(V^2)$ （使用简单的数组实现）或 $\log V)$ （使用优先队列实现），其中 $V$ 是顶点数， $E$ 是边数。
- 弗洛伊德算法：时间复杂度为 $O(V^3)$ ，其中 $V$ 是顶点数。对于大型图，这可能比迪杰斯特拉算法慢。
处理负权边：
- 迪杰斯特拉算法：不能正确处理包含负权边的图，因为负权边可能导致算法无法正确更新最短路径。
- 弗洛伊德算法：可以处理负权边，但必须确保图中没有负权环，否则算法无法找到正确的最短路径。
数据结构：
- 迪杰斯特拉算法：通常使用优先队列（如最小堆）来选择下一个最近的顶点。
- 弗洛伊德算法：通常使用二维数组来存储所有顶点对之间的最短路径信息。
初始化：
- 迪杰斯特拉算法：需要初始化源点到所有其他顶点的距离，源点到自己的距离为0，到其他顶点的距离为无穷大。
- 弗洛伊德算法：需要初始化一个 $\times V$ 的距离矩阵，其中对角线元素为0，其他元素为边的权重或无穷大（如果顶点间没有直接的边）。