Bellman-Ford算法

  1 #include<stdio.h>
  2 #define max 0xffffff
  3 int g[20001][20001];    //图的邻接矩阵
  4 int dist[20001];
  5 int n;//顶点个数
  6 int m;//边个数
  7 struct Edge
  8 {
  9     int u, v, w;    //边：起点、终点、权值
 10 };
 11 Edge e[200001];
 12 bool bellman_ford(int n)//bellman-ford算法
 13 {
 14     int i, k, t,j;
 15     for(i=0;i<n;i++)
 16         dist[i]=g[0][i];//初始化
 17     for(i=1;i<=n-1;i++)
 18     {
 19 
 20     /*假设第k条边的起点是u,终点是v,以下循环考虑第k条边是否会使得源点v0到v的
 21         最短距离缩短,即判断dist[edges[k].u] + edges[k].w < dist[edges[k].v] 是否成立*/
 22         for(j=0;j<n;j++)
 23         {
 24             printf("%d ",dist[j]);
 25         }
 26        printf("\n");
 27         for(k=1;k<=m;k++)
 28         {
 29             t=dist[e[k].u]+e[k].w;
 30             if(dist[e[k].u]<max&&t<dist[e[k].v])
 31             {
 32                 dist[e[k].v] = t;
 33             }
 34         }
 35     }
 36     /*以下是检查，若还有更新则说明存在无限循环的负值回路*/
 37     for(k = 0; k < m; k ++)
 38     {
 39         if(dist[e[k].u] != max &&dist[e[k].u] + e[k].w < dist[e[k].v])
 40         {
 41             return false;
 42         }
 43     }
 44     return true;
 45 }
 46 
 47 int main()
 48 {
 49     scanf("%d %d",&n,&m);
 50     int i,j;
 51     for(i=0;i<n;i++)
 52     {
 53         for(j=0;j<n;j++)
 54             g[i][j]=max;
 55         g[i][i]=0;
 56     }
 57     for(i=1;i<=m;i++)
 58     {
 59         int a,b,c;
 60         scanf("%d %d %d",&a,&b,&c);
 61         e[i].u=a;
 62         e[i].v=b;
 63         e[i].w=c;
 64         g[a][b]=c;
 65     }
 66     for(i=0;i<n;i++)
 67     {
 68         for(j=0;j<n;j++)
 69             printf("%d ",g[i][j]);
 70         printf("\n");
 71     }
 72     bellman_ford(n);
 73     for(i=0;i<n;i++)
 74     {
 75         printf("%d\n",dist[i]);
 76     }
 77 
 78     return 0;
 79 }
 80 
 81 
 82 
 83 /*
 84 
 85   7 10
 86   0 1 6
 87   0 2 5
 88   0 3 5
 89   1 4 -1
 90   2 1 -2
 91   2 4 1
 92   3 2 -2
 93   3 5 -1
 94   4 6 3
 95   5 6 3
 96   
 97 Press any key to continue
 98 
 99 
100 */