bellman_ford算法

给定一个源点，求最短路径，那么存在以源点为根的最短路径树
因为最短路径具有最优子结构的性质，所以我们可以先求出树的第一层，然后再求出树的第二层，以此类推
bellman_ford算法就是按照这种思想求最短路径的。
因为树最多有n-1层，所以只要n-1次循环即可，每次循环i访问所有的边，然后松弛路径，就求出了第i层的最短路径。
那么很明显，该算法的时间复杂度为O(VE)

http://acm.fafu.edu.cn/problem.php?id=1473

#include <stdio.h>
#include <string.h>
const int N = 2000+10;
const int INF = 1<<30;
struct Edge
{
    int u,v,weight;
}g[4000000];
int dist[N];
void relax(int u, int v,int weight)
{
    if(dist[v] > dist[u] + weight)
        dist[v] = dist[u] + weight;
}
void bellman_ford(int n, int m)
{
    int i,j;
    for(i=0; i<n-1; ++i)//n-1循环
        for(j=0; j<m; ++j)//枚举所有的边去松弛最短路径
        {
            relax(g[j].u,g[j].v,g[j].weight);
        }    
}
int main()
{
    int n,m,a,b,c,i;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=1; i<=n; ++i)
            dist[i] = INF;
        for(i=0; i<m; ++i)
        {
            scanf("%d%d%d",&g[i].u,&g[i].v,&g[i].weight);
            if(g[i].u==1)
                dist[g[i].v] = g[i].weight;
        }        
        bellman_ford(n,m);
        for(i=2; i<=n; ++i)
            printf("%d
",dist[i]);
    }        
    return 0;
}