単一始点最短路 (Bellman Ford)

概要

単一始点最短経路問題を解くアルゴリズムです．ある 2 頂点間の距離を，その間の辺を使って短く更新できる限り更新するということを繰り返します．

計算量

$O(EV)$

使い方

負のループも OK．始点から到達可能な負のループがあると second が false になる．

実装

std::pair<std::vector<Weight>, bool> bellmanFord(const Graph &g, int s) {
    int n = g.size();
    const Weight inf = std::numeric_limits<Weight>::max() / 8;
    Edges es;
    for (int i = 0; i < n; i++)
        for (auto &e : g[i]) es.emplace_back(e);
    std::vector<Weight> dist(n, inf);
    dist[s] = 0;
    bool negCycle = false;
    for (int i = 0;; i++) {
        bool update = false;
        for (auto &e : es) {
            if (dist[e.src] != inf && dist[e.dst] > dist[e.src] + e.weight) {
                dist[e.dst] = dist[e.src] + e.weight;
                update = true;
            }
        }
        if (!update) break;
        if (i > n) {
            negCycle = true;
            break;
        }
    }
    return std::make_pair(dist, !negCycle);
}

検証

AOJ GLP1B (Submission)