图论算法之最短路径之Bell-Ford算法算法

1、基本思想
它是最优性原理的直接应用，算法基于以下事实：
（1）如果最短路径存在，则每个顶点最多经过一次，因此不超过n-1条边。
（2）长度为k的路径由长度为k-1的路加一条边得到。
（3）由最优性原理，只需依次考虑长度为1,2，...，k-1的最短路径。
2、步骤
对每条边边进行|V|-1次Relax(松弛)操作。
如果存在（u，v）属于E，使得dis[u]+w<dis[v],则存在负权回路；否则dis[v]即为s到v的最短距离，pre[v]为前驱。
Bell-Ford实质上就是一个迭代处理过程。
3、样例代码

//Bellman-Ford map[i][j]==MaxInt means no direct path from i to j
void bellman_ford() {
    bool notfinish=false;
    memset(checked,0,sizeof(checked));
    checked[s]=true;
    for(k=0; k<n&&!notfinish; k++) {
        notfinish=true;
        for(i=0; i<n; i++) {

        }
    }
}