图论 Floyd算法

青旅半醒 2021-12-15 05:01 257阅读 0赞

**Floyd算法　　**

**　　时间复杂度O (n^3)**

**　　空间复杂度O (n^2)**

**用处**

可以求任意两个点之间的最短路径长度。

得出的邻接矩阵存储 i 到 j 的最短路径长度。

无法解决“负权环问题”

1 \_\_\_\_ -2

\\　　/

**思路（摘自[知乎][Link 1]作者-赵轩昂）**

采用动态规划思想，![f\[k\]\[i\]\[j\]][f_k_i_j]表示![i][]和![j][]之间可以通过编号不超过![k][](![1...k][])的节点的最短路径。

*初值![f\[0\]\[i\]\[j\]][f_0_i_j]为原图的邻接矩阵。*

则![f\[k\]\[i\]\[j\]][f_k_i_j]可以从![f\[k-1\]\[i\]\[j\]][f_k-1_i_j]转移来，表示![i][]到![j][]不经过![k][]这个节点。  
也可以从![f\[k-1\]\[i\]\[k\]+f\[k-1\]\[k\]\[j\]][f_k-1_i_k_f_k-1_k_j]转移过来，表示经过![k][]这个点。  
意思即![f\[k\]\[i\]\[j\] = min(f\[k-1\]\[i\]\[j\] , f\[k-1\]\[i\]\[k\]+f\[k-1\]\[k\]\[j\])][f_k_i_j_ _ min_f_k-1_i_j_ _ f_k-1_i_k_f_k-1_k_j]

然后你就会发现![f][]最外层一维空间可以省略，因为![f\[k\]][f_k]只与![f\[k-1\]][f_k-1]有关。

**初始化**

用邻接矩阵表示，

f\[i\]\[j\]初始化为 i 到 j 的距离，

如果 i 无法到达 j 则 f\[i\]\[j\] = INF;

//初始化 
    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            if(i==j)
                f[i][j] = 0;
            else
                f[i][j] = INF;
        }
    }
    //读入边
    for(int i=1;i<=m;i++){
        cin >> t1 >> t2 >> t3;
        f[t1][t2] = t3;
    }

**核心代码:**

for(int k=0;k<n;++k){
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                f[i][j] = min(f[i][j],f[i][k] + f[j][k]);
            }
        }
    }

转载于:https://www.cnblogs.com/--zz/p/10623044.html

[Link 1]: https://www.zhihu.com/question/30955032
[f_k_i_j]: https://www.zhihu.com/equation?tex=f%5Bk%5D%5Bi%5D%5Bj%5D
[i]: https://www.zhihu.com/equation?tex=i
[j]: https://www.zhihu.com/equation?tex=j
[k]: /images/20211214/064b4d55574d4800bf3223fd57d2254e.png
[1...k]: /images/20211214/38efda61e81c4e48be15007aac521409.png
[f_0_i_j]: /images/20211214/71d5ba04245f43b89b7c81301e357f60.png
[f_k-1_i_j]: https://www.zhihu.com/equation?tex=f%5Bk-1%5D%5Bi%5D%5Bj%5D
[f_k-1_i_k_f_k-1_k_j]: https://www.zhihu.com/equation?tex=f%5Bk-1%5D%5Bi%5D%5Bk%5D%2Bf%5Bk-1%5D%5Bk%5D%5Bj%5D
[f_k_i_j_ _ min_f_k-1_i_j_ _ f_k-1_i_k_f_k-1_k_j]: https://www.zhihu.com/equation?tex=f%5Bk%5D%5Bi%5D%5Bj%5D+%3D+min%28f%5Bk-1%5D%5Bi%5D%5Bj%5D+%2C+f%5Bk-1%5D%5Bi%5D%5Bk%5D%2Bf%5Bk-1%5D%5Bk%5D%5Bj%5D%29
[f]: https://www.zhihu.com/equation?tex=f
[f_k]: https://www.zhihu.com/equation?tex=f%5Bk%5D
[f_k-1]: https://www.zhihu.com/equation?tex=f%5Bk-1%5D