注意: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 ) O(V^2) O(V2)(使用简单的数组实现)或 O ( ( V + E ) log V ) O((V+E) \log V) O((V+E)logV)(使用优先队列实现),其中 V V V 是顶点数, E E E 是边数。
- 弗洛伊德算法:时间复杂度为 O ( V 3 ) O(V^3) O(V3),其中 V V V 是顶点数。对于大型图,这可能比迪杰斯特拉算法慢。
-
处理负权边:
- 迪杰斯特拉算法:不能正确处理包含负权边的图,因为负权边可能导致算法无法正确更新最短路径。
- 弗洛伊德算法:可以处理负权边,但必须确保图中没有负权环,否则算法无法找到正确的最短路径。
-
数据结构:
- 迪杰斯特拉算法:通常使用优先队列(如最小堆)来选择下一个最近的顶点。
- 弗洛伊德算法:通常使用二维数组来存储所有顶点对之间的最短路径信息。
-
初始化:
- 迪杰斯特拉算法:需要初始化源点到所有其他顶点的距离,源点到自己的距离为0,到其他顶点的距离为无穷大。
- 弗洛伊德算法:需要初始化一个 V × V V \times V V×V 的距离矩阵,其中对角线元素为0,其他元素为边的权重或无穷大(如果顶点间没有直接的边)。
总结来说,选择哪种算法取决于具体问题的需求,如果需要找到单个源点到所有其他顶点的最短路径,且图中没有负权边,迪杰斯特拉算法是更好的选择。如果需要找到所有顶点对之间的最短路径,或者图中可能存在负权边,弗洛伊德算法可能更适合。
标签:int,短路,迪杰,算法,Floyd,斯特拉,顶点,AcWing854,负权 From: https://blog.csdn.net/weixin_46028606/article/details/141612747