任意两点间的最短路问题 Floyd-Warshall算法的简单应用

我就是我 2023-07-12 05:06 83阅读 0赞

这一算法与之前的Bellman-F=Ford算法一样，都可以判断负环

只需要检查dp \[i\] \[j\] 是负数的顶点i即可

1 // 求解任意两点间的最短路径问题
     2 // Floyed-Warshall算法
     3 // 复杂度O(N^3),N为顶点数
     4 
     5 #include <cstdio>
     6 #include <iostream>
     7 
     8 using namespace std;
     9 // 用dp的思路来求解
    10 // dp[k][i][j]:从i到j，只利用前K个节点的最短路
    11 // dp[k][i][j]=dp[k-1][i][k] + dp[k-1][k][j]
    12 // 由于后一层所需的，都来自前一层，而前一层所需
    13 // 然后在考虑循环顺序，定k，并且维护最小，所以中间元素必定使用之前维护的在k行k列的元素
    14 // 而维护最小值时，k行k列元素，在循环中，加和一定大于原来的值（否则存在d[i][j]<0,存在负圈)
    15 // 所以维护最小值时不更新，依旧是上一列表中的值
    16 // 所以dp数组可以降维进行运算
    17 
    18 const int max_N = 200+2;
    19 const int max_E = 10000+2;
    20 const int INF = 1e9;
    21 
    22 int dp[max_N][max_N];
    23 int N,E;
    24 
    25 void floyd_warshall()
    26 {
    27     for(int k=0;k<N;++k)
    28     {
    29         for(int i=0;i<N;++i)
    30         {
    31             for(int j=0;j<N;++j)
    32             {
    33                 dp[i][j]=min( dp[i][j],dp[i][k]+dp[k][j] );
    34             }
    35         }
    36     }
    37 }
    38 
    39 int main()
    40 {
    41     scanf("%d %d",&N,&E);
    42     int a,b,c;
    43     for(int i=0;i<N;++i)
    44     {
    45         for(int j=0;j<N;++j)
    46         {
    47             if(i==j)
    48             {
    49                 dp[i][j]=0;
    50             }
    51             else
    52             {
    53                 dp[i][j]=INF;
    54             }
    55         }
    56     }
    57     for(int i=0;i<E;++i)
    58     {
    59         scanf("%d %d %d",&a,&b,&c);
    60         dp[a][b]=c;
    61         // 无向图
    62         dp[b][a]=c;
    63     }
    64     floyd_warshall();
    65 
    66     for(int i=0;i<N;++i)
    67     {
    68         for(int j=0;j<N;++j)
    69         {
    70             printf("%d ",dp[i][j]);
    71         }
    72         printf("\n");
    73     }
    74     return 0;
    75 }
    76 /*
    77 7 10
    78 0 1 2
    79 0 2 5
    80 1 2 4
    81 1 3 6
    82 1 4 10
    83 2 3 2
    84 3 5 1
    85 4 5 3
    86 4 6 5
    87 5 6 9
    88 
    89 
    90 
    91 
    92 0 2 5 7 11 8 16
    93 2 0 4 6 10 7 15
    94 5 4 0 2 6 3 11
    95 7 6 2 0 4 1 9
    96 11 10 6 4 0 3 5
    97 8 7 3 1 3 0 8
    98 16 15 11 9 5 8 0
    99 */