数据结构与算法-进阶(十四)最短路径&Floyd 算法

数据结构与算法-进阶(十四)最短路径&Floyd 算法摘要Floyd 算法是可以计算出任意两个顶点之间的最短路径。它的核心原理基于这样一个共识,即两个顶点之间的最短路径的情况要么是两个顶点之间直接连

大家好,欢迎来到IT知识分享网。数据结构与算法-进阶(十四)最短路径&Floyd

摘要

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

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信