今天开始学算法系列 -- bellman ford

   bellmanford算法是通用的单源最短路径求解算法，相比Dijkstra，复杂度稍差 ， 但是可以处理含有负边的图路径问题，所以比较适合通用的图。
  这里给出对于该算法的伪代码：
  all V:
  d(v) = INF;
  for(i = 0; i< |V| ; i++)
        for(j = 0; j<|E|;j++)
            update d(i)
  从伪代码可以看出 ， bellman算法是对每一条边都做一次跟新操作，如果每条边都无需再更新的时候，单源最短路径问题也就求出来了
  bellman算法对于负环存在的问题， 也很容易求解，如果存在负环，必然会存在i = |V| - 1的情况，所以只要在适当的时候对这个值进行判断就可以知道是否存在负环了
  
  下面是实现的代码：
   

typedef struct edge_st
{
    int from;
    int to;
    int cost;
}edge;
#define MAXEDGE 5
#define MAXV 4
int d[MAXV] = { 0 };
edge es[MAXEDGE] = { 0 };

void init()
{
    edge es1 = { 0, 1, 2 };
    edge es2 = { 3, 0, 2 };
    edge es3 = { 0, 2, 5 };
    edge es4 = { 3, 1, 6 };
    edge es5 = { 2, 3, 2 };
    es[0] = es1;
    es[1] = es2;
    es[2] = es3;
    es[3] = es4;
    es[4] = es5;
}

#define INF 100000

int _tmain(int argc, _TCHAR* argv[])
{
    init();
    for (int i = 0; i < MAXV; i++)
    {
        d[i] = INF;
    }
    d[0] = 0;
    bool update = true; //设置更新标志， 如果每条边都没有跟新了就为false
    for (int j = 0; j < MAXV; j++)
    {
        if (!update)
        {
            printf("has find the shortest path\n");
            break;
        }
        update = false;
        for (int i = 0; i < MAXEDGE; i++)
        {
            if (d[es[i].from] != INF && d[es[i].to] > es[i].cost + d[es[i].from])
            {
                d[es[i].to] = d[es[i].from] + es[i].cost;
                update = true;
            }
        }
        if (j == (MAXV - 1))
        {
            printf("The edge is negative loop\n"); //判断是否有负环存在
            return 0;
        }
    }

    for (int i = 0; i < MAXV; i++)
    {
        printf("%d\n",d[i]);
    }
    return 0;
}