大家好,欢迎来到IT知识分享网。
摘要
Floyd 算法是可以计算出任意两个顶点之间的最短路径。它的核心原理基于这样一个共识,即两个顶点之间的最短路径的情况要么是两个顶点之间直接连接,要么就是通过其他顶点连接。
Floyd 算法是多源最短路径算法,能够求出任意2个顶点之间的最短路径,并允许存在负权边。
Floyd 算法的基本原理大致是这样的。首先要明确这个点,就是任意顶点 i 到任意顶点 j 的最短路径只有两种情况。即要么顶点 i 直接到顶点 j,要么顶点 i 经过若干个顶点到顶点 j。
如果这个点能达成一致,接下来就可以做个假设。假设 dist(i, j) 表示顶点i 到顶点 j 的最短路径。那么就可以任意顶点 k 到顶点 i 和顶点 j 的最短路径表示为 dist(i, k) 和 dist (k, j)。
那么顶点 i、顶点 j 的路径就可以表示为 dist(i, k) + dist(k, j)。接下来就是做这样的判断,就是 dist(i, k) + dist(k, j) < dist(i, j):
- 如果成立,则 dist(i, j) = dist(i, k) + dist(k, j),表示的意思就是顶点 i 经过顶点k 到达顶点 j 比直接到达顶点 j 的路径短;
当遍历完所有的顶点之后,dist(i, j) 中记录的就是顶点i 到达顶点 j 的最短路径了。
到这里,Floyd 算法的原理算是讲完了。下面上代码:
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if dist(i, k) + dist(k, j) < dist(i, j) {
dist(i, j) = dist(i, k) + dist(k, j)
}
}
}
}
通过代码可以看出 Floyd 算法的时间复杂度是 O(V^3^),V 是顶点的数量。
总结
- 两个顶点之间的最短路径有两种情况,一种是两个顶点直接连接,另外一种是通过其他顶点连接;
- Floyd 算法就是基于 dist(i, k) + dist(k, j) < dist(i, j) 做处理;
- Floyd 算法支持负权边。
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/52043.html