Bellman-Fordアルゴリズム

以前の最短パスアルゴリズムで述べたように,すべてのエッジをすべて失効するまでリラックスすれば最短パスを得ることができる.
注意:図に負の輪はありません.そうでなければ、負のリングのある点がこの負のリングのすべてのエッジの緩和操作を通過すると、この点のd[i]が減少し、この負のリングの緩和操作によってそれ自体が絶えず小さくなることが分かった.負のループが存在する図については,最短では意味がない.
そこでエッジに関するアルゴリズムは,エッジ間の関係に注目する必要はなく,すべてのエッジをリラックスさせるだけでよい.
テンプレートの挿入:

struct edge {int from, to, cost};

edge es[MAX_E]; //  

int d[MAX_V];
int V, E;

for (int i = 1; i <= V; i++) d[i] = INF;
d[s] = 0;
while (true) {
    bool update = false;
    for (int i = 1; i <= E; i++) {
        edge e = es[i];
        //d[e.from]=INF       ，     
        if (d[e.from]!=INF && d[e.to]>d[e.from]+e.cost]) {
            d[e.to] = d[e.from] + cost;
            update = true;
        }
    }
    if (!update) break;
}