最短問題Bellman-Fordアルゴリズム

Bellman-Fordアルゴリズムは負の重みを含む単一ソースの最短経路を解くために用いられるが,負の重みが存在する場合,最短回路は必ずしも存在しないため,このアルゴリズムは負のループの存在を判断することができる.
考え方もコードも簡単です.
求めた最短路は必ずリングを含まないので、通過したノードはn-1個(起点を除いた)である.
n-1回の操作を行い、各エッジを検査するたびに、緩和操作を行う.
さらに各辺を検査し、まだ緩むことができれば、必ず負のリングが存在し、最短路は存在しない.
そうでなければ存在します.
本当のことを言うと、最短回路アルゴリズムの感覚と最小生成ツリーの構想とアルゴリズムは特に似ている.

const int inf=0x3f3f3f3f;
struct Edge
{
    int from;
    int to;
    int weight;
}edge[10000];
int N;//   
int i;//    
int dis[2501];
bool BellmanFord()
{
    bool flag;
    for(int j=0;j<N-1;++j)
    {
        flag=false;
        for(int k=0;k<i;++k)
        {
            if(dis[edge[k].to]>dis[edge[k].from]+edge[k].weight)
            {
                dis[edge[k].to]=dis[edge[k].from]+edge[k].weight;
                flag=1;
            }
        }
        if(!flag)
            break;
    }
    for(int j=0;j<i;++j)
    {
        if(dis[edge[j].to]>dis[edge[j].from]+edge[j].weight)
            return true;//    
    }
    return false;//    
}