单源最短路 Bellman-Ford算法（有向图）

绝地灬酷狼 2023-07-12 05:06 10阅读 0赞

1 // 单源最短路问题
     2 // Bellman-Ford算法
     3 // 复杂度O(V*E)
     4 
     5 //! 可以判断负圈
     6 
     7 
     8 #include <cstdio>
     9 #include <iostream>
    10 
    11 // 最大边数
    12 const int max_E=10000+2;
    13 // 最大定点数
    14 const int max_N=1000+2;
    15 const int INF=1e9;
    16 
    17 using namespace std;
    18 // 定义边结构体edge
    19 struct edge
    20 {
    21     int from,to,cost;
    22 };
    23 
    24 edge es[max_E];
    25 
    26 int d[max_N];
    27 int N,E;
    28 
    29 void shortest_path(int s)
    30 {
    31     for(int i=0;i<N;++i)
    32     {
    33         d[i]=INF;
    34     }
    35     d[s]=0;
    36 
    37     while(true)
    38     {
    39         bool update=false;
    40         // 每次更新都要遍历所有的边
    41         for(int i=0;i<E;++i)
    42         {
    43             edge e=es[i];
    44             if(d[e.from]!=INF && d[e.to]>d[e.from]+e.cost)
    45             {
    46                 d[e.to]=d[e.from]+e.cost;
    47                 update=true;
    48             }
    49         }
    50         if(update==false)
    51         {
    52             break;
    53         }
    54     }
    55 }
    56 
    57 
    58 int main()
    59 {
    60     scanf("%d %d",&N,&E);
    61     for(int i=0;i<E;++i)
    62     {
    63         scanf("%d %d %d",&es[i].from,&es[i].to,&es[i].cost);
    64     }
    65     shortest_path(0);
    66     for(int i=0;i<N;++i)
    67     {
    68         printf("%d ",d[i]);
    69     }
    70     return 0;
    71 }
    72 
    73 /*
    74 7 10
    75 0 1 2
    76 0 2 5
    77 1 2 4
    78 1 3 6
    79 1 4 10
    80 2 3 2
    81 3 5 1
    82 4 5 3
    83 4 6 5
    84 5 6 9
    85 
    86 */

// 单源最短路问题// Bellman-Ford算法// 复杂度O(V\*E)  
//! 可以判断负圈  
  
\#include <cstdio>\#include <iostream>  
// 最大边数const int max\_E=10000+2;// 最大定点数const int max\_N=1000+2;const int INF=1e9;  
using namespace std;// 定义边结构体edgestruct edge\{ int from,to,cost;\};  
edge es\[max\_E\];  
int d\[max\_N\];int N,E;  
void shortest\_path(int s)\{ for(int i=0;i<N;++i) \{ d\[i\]=INF; \} d\[s\]=0;  
while(true) \{ bool update=false; // 每次更新都要遍历所有的边 for(int i=0;i<E;++i) \{ edge e=es\[i\]; if(d\[e.from\]!=INF && d\[e.to\]>d\[e.from\]+e.cost) \{ d\[e.to\]=d\[e.from\]+e.cost; update=true; \} \} if(update==false) \{ break; \} \}\}  
  
int main()\{ scanf("%d %d",&N,&E); for(int i=0;i<E;++i) \{ scanf("%d %d %d",&es\[i\].from,&es\[i\].to,&es\[i\].cost); \} shortest\_path(0); for(int i=0;i<N;++i) \{ printf("%d ",d\[i\]); \} return 0;\}  
/\*7 100 1 20 2 51 2 41 3 61 4 102 3 23 5 14 5 34 6 55 6 9  
\*/