1.多源最短路简介:
我们知道单源最短路是指从某一个源点到图中的其它顶点的最短路。
多源最短路就是指每一个点到图中其他顶点的最短路。
那么有的人肯定想我知道求单源最短路的算法了,那么有多少个点我就求多少次呗,这样做时间效率不高,空间效率也极其低。
那么有什么算法求解多源最短路呢?——Floyd
2.Floyd简介:
3.三维空间Floyd核心代码:
1 int g[N][N]; // 邻接矩阵存图 2 int dp[N][N][N]; 3 void floyd(int n) { 4 for (int k = 0; k <= n; ++k) { 5 for (int i = 1; i <= n; ++i) { 6 for (int j = 1; j <= n; ++j) { 7 if (k == 0) { 8 dp[k][i][j] = g[i][j]; 9 } else { 10 dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]); 11 } 12 } 13 } 14 } 15 }
4.Floyd空间优化:
![](/i/l/?n=23&i=blog/2727880/202303/2727880-20230314201335243-202117491.png)
怎么确定状态转移的?
看下图
我们发现从顶点1到顶点4有三条路径
dp[0][1][4]就相当于图中的g[1][4]这里采用邻接矩阵的形式
然后k作为中介点可以使2,3
那么dp[2][1][4] = dp[2][1][2] + dp[2][2][4]
也就是我们可以简化为dp[1][4] = dp[1][2] + dp[2][4]
V1到V4等于V1到V2加上V2到V4,可以理解吧。
然后V1到V4还可以等于V1到V3加上V3到V4
即最后的最短路就是dp[1][4] = min(g[1][4], min(g[1][2] + g[2][4]
, g[1][3] + g[3][4]))
优化空间后的Code
1 int g[N][N]; 2 void floyd(int n) { 3 for (int k = 1; k <= n; ++k) { 4 for (int i = 1; i <= n; ++i) { 5 for (int j = 1; j <= n; ++j) { 6 g[i][j] = min(g[i][j], g[i][k] + g[k][j]); 7 } 8 } 9 } 10 }
转载自:https://blog.csdn.net/lytwy123/article/details/90214622
标签:int,短路,算法,Floyd,多源,dp From: https://www.cnblogs.com/jyssh/p/17216196.html