ベルマンフォード法
(graph/shortestpath/bellmanford.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "graph/shortestpath/bellmanford.hpp"

概要

単一始点最短路. 負閉路検出ができる.

計算量

$O(EV)$

使用例

• bellmanford(g, frm) : frmからベルマンフォード法.
  • 返り値の型 : vector<T>
  • 負閉路があったら空のvectorを返す.

Verified with

• test/aoj/GRL_1_B.test.cpp

Code

/**
* @brief ベルマンフォード法
* @docs docs/graph/shortestpath/bellmanford.md
*/

template <typename T>
vector<T> bellmanford(const Graph<T>& g, int frm) {
    vector<T> ret(g.V, GINF<T>);
    ret[frm] = 0;
    for (int i = 0; i < g.V - 1; ++i) {
        for (int j = 0; j < g.V; ++j) {
            for (auto& e : g.mat[j]) {
                if (ret[e.frm] == GINF<T>) continue;
                ret[e.to] = min(ret[e.to], ret[e.frm] + e.cst);
            }
        }
    }
    for (int j = 0; j < g.V; ++j) {
        for (auto& e : g.mat[j]) {
            if (ret[e.frm] == GINF<T>) continue;
            if (ret[e.frm] + e.cst < ret[e.to]) return vector<T>();
        }
    }
    return ret;
}

#line 1 "graph/shortestpath/bellmanford.hpp"
/**
* @brief ベルマンフォード法
* @docs docs/graph/shortestpath/bellmanford.md
*/

template <typename T>
vector<T> bellmanford(const Graph<T>& g, int frm) {
    vector<T> ret(g.V, GINF<T>);
    ret[frm] = 0;
    for (int i = 0; i < g.V - 1; ++i) {
        for (int j = 0; j < g.V; ++j) {
            for (auto& e : g.mat[j]) {
                if (ret[e.frm] == GINF<T>) continue;
                ret[e.to] = min(ret[e.to], ret[e.frm] + e.cst);
            }
        }
    }
    for (int j = 0; j < g.V; ++j) {
        for (auto& e : g.mat[j]) {
            if (ret[e.frm] == GINF<T>) continue;
            if (ret[e.frm] + e.cst < ret[e.to]) return vector<T>();
        }
    }
    return ret;
}

Back to top page