(単一ソース最短)Bellman-Fordアルゴリズム

Bellman-Fordアルゴリズムは負の重みを含む単一ソースの最短パスを求めるアルゴリズムであり,効率は低いが,コードは書きやすい.その原理は、弛緩を継続的に行い(原文はこう書いてあるが、なぜ弛緩と呼ぶのか、議論が大きい)、弛緩のたびに各辺を更新し、n-1回弛緩した後に更新できると説明図に負のループがあるため、結果が得られず、そうでなければ完成する.Bellman-Fordアルゴリズムには小さな最適化があります.緩和のたびに識別flagが設定され、初期値はFALSEであり、エッジ更新があればTRUEに割り当てられ、最終的にはFALSEであれば直接終了に成功します.

struct edge {
    int from,to;
    int cost;
};
edge es[MAXE];
int d[MAXV]; // d[i]  d[start] i      
int v, e; //    ，   

void Bellman_Ford(int s) {
    fill(d + 1, d + v + 1, INF);
    d[s] = 0;

    for (int i = 1; i <= v; ++i) {
        bool update = false;
        for (int j = 0; j < e; ++j) {
            if (d[es[j].from] != INF) {
                d[es[j].to] = min(d[es[j].to], d[es[j].from] + es[j].cost);
                update = true;
            }
        }
        if (!update)
            break;
    }
    
    bool flag = false;
    for (int i = 0; i < es.size(); ++i) {
        if (d[es[i].to] > d[es[i].from] + es[i].cost) {
            flag = true;
            break;
        }
    }
    if (flag)
        cout << "       ";
}