任意两点最短路 Floyd-Warshall算法 传递闭包

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])

使用转动数组,就能够写成2维数组的情势
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])便可(预处理也要变化)

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 任意两点最短路 Floyd-Warshall算法 传递闭包

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡