图论 Floyd算法

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

Floyd算法　　

　　时间复杂度O (n^3)

　　空间复杂度O (n^2)

用处

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

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

　　无法解决“负权环问题”

　　1 ____ -2

　　　\　　/

　　　　3

思路（摘自知乎作者-赵轩昂）

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

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

则f\[k\]\[i\]\[j\]可以从f\[k-1\]\[i\]\[j\]转移来，表示i到j不经过k这个节点。
也可以从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最外层一维空间可以省略，因为f\[k\]只与f\[k-1\]有关。

初始化

　　用邻接矩阵表示，

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

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

  1. //初始化 
  2. for(int i=0;i<N;++i){
  3.     for(int j=0;j<N;++j){
  4.         if(i==j)
  5.             f[i][j] = 0;
  6.         else
  7.             f[i][j] = INF;
  8.     }
  9. }
  10. //读入边
  11. for(int i=1;i<=m;i++){
  12.     cin >> t1 >> t2 >> t3;
  13.     f[t1][t2] = t3;
  14. }

核心代码:

  1. for(int k=0;k<n;++k){
  2.     for(int i=0;i<n;++i){
  3.         for(int j=0;j<n;++j){
  4.             f[i][j] = min(f[i][j],f[i][k] + f[j][k]);
  5.         }
  6.     }
  7. }

　　

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

发表评论

表情：
评论列表 （有 0 条评论，336人围观）

还没有评论，来说两句吧...

相关阅读

    相关 图论算法

    Problem1一笔画问题 题目描述     给出一个图，求其欧拉回路（若没有回路，则求其欧拉路径），若不存在则输出‘No solution’ 输入     输入的第一

    妖狐艹你老母妖狐艹你老母/ 0 赞/ 335 阅读

    相关 图论 Floyd算法

    Floyd算法　　 　　时间复杂度O (n^3) 　　空间复杂度O (n^2) 用处 　　可以求任意两个点之间的最短路径长度。 　　得出的邻接矩阵存储 i 到 j 的

    青旅半醒青旅半醒/ 0 赞/ 337 阅读