任意两点最短路 Floyd-Warshall算法 传递闭包
发布时间：2020-12-13 20:16:02 所属栏目：PHP教程 来源：网络整理
导读：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的最短
|
Floyd-Warshall算法是求解任意两点最短路的有力武器。其也适用于存在负边的情况。 DP思路，假定只使用前K个点时i到j的最短距离为d[k][i][j] 使用转动数组，就能够写成2维数组的情势 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算法来进行传递闭包。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |