14、数据结构与算法进阶:最短路径、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(V3),V 是顶点的数量。

总结

  • 两个顶点之间的最短路径有两种情况,一种是两个顶点直接连接,另外一种是通过其他顶点连接;
  • Floyd 算法就是基于 dist(i, k) + dist(k, j) < dist(i, j) 做处理;
  • Floyd 算法支持负权边。

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: