任意两点最短路 Floyd-Warshall算法 传递闭包
浏览数：26 /
时间：2015年06月08日
Floyd-Warshall算法是求解任意两点最短路的有力武器。其也适用于存在负边的情况。
DP思路，假设只使用前K个点时i到j的最短距离为d[k][i][j]
那么，使用前K+1个点就可以分成两种情况
①i到j的最短路用到了第K+1个点(d[k+1][i][j] = d[k][i][j])
②i到j的最短路没有用到第K+1个点(d[k+1][i][j] = d[k][i][k]+d[k][k][j]);
所以，d[k+1][i][j] = min(d[k][i][j],d[k][i][k]+d[k][k][j])
使用滚动数组，就可以写成二维数组的形式
d[i][j] = min(d[i][j],d[i][k]+d[k][j])
Floyd算法可以在O(V^3)的时间内解出，判断图中是否有负圈，只需要检查是否存在d[i][i]是负数的顶点i就可以了。
代码
//d[i][j]表示i->j的权值，不存在时设为INF 但是d[i][i]设为0
for(int k = 0 ; k < V ; k ++) {
for(int i = 0 ; i < V ; i ++) {
for(int j = 0 ; j < V ; j ++) {
d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}
}
}由于实现起来非常简单，如果复杂度在可以承受的范围之内，单源最短路也可以使用Floyd-Warshall算法来进行求解。
在有向图中，如果需要判断每两个点是否存在路径，那么也可以用Floyd算法来进行传递闭包。
只需要改成d[i][j] = d[i][j] || (d[i][k]&&d[k][j])即可(预处理也要变化)
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
