$\newcommand{\O}{\mathrm{O}}$
負辺を含むグラフに対する単一始点最短経路問題(SSSP) を効率よく解くことができるアルゴリズム. また負の有向閉路の検出(3種類)も同じ計算量で行うことが可能.
全辺を見て始点からの最短距離が更新されるなら更新するという操作を $n$ 回行う. それ以降もなお最短距離が更新される場合は始点から到達可能な負の有向閉路が存在することになる.
(関数)
add_edge$(u, v, cost)$ : $u$ から $v$ に向かう重み $cost$ の有向辺を追加する
solve$(s)$ : $s$ を始点として各頂点までの最短距離を求める
時間計算量: $\O (nm)$
template<typename T> class bellman_ford { public: struct edge{ int from, to; T cost; }; int V; T inf; vector<T> d; vector<edge> es; bellman_ford(int node_size) : V(node_size), inf(numeric_limits<T>::max()/2), d(V, inf){} void add_edge(int from, int to, T cost){ es.push_back((edge){from, to, cost}); } //sからの最短路長およびsからたどり着ける負の閉路の検出(trueなら負の閉路が存在する) bool solve(int s){ int cnt = 0; d[s] = 0; while(cnt < V){ bool update = false; for(auto& e : es){ if(d[e.from] != inf && d[e.to] > d[e.from] + e.cost){ d[e.to] = d[e.from] + e.cost; update = true; } } if(!update) break; cnt++; } return (cnt == V); } //すべての負の閉路の検出(trueなら負の閉路が存在する) bool find_negative_loop(){ fill(d.begin(), d.end(), (T)0); int cnt = 0; while(cnt < V){ bool update = false; for(auto& e : es){ if(d[e.to] > d[e.from] + e.cost){ d[e.to] = d[e.from] + e.cost; update = true; } } if(!update) break; cnt++; } return (cnt == V); } // s, t 間の最短距離が非有界 bool shortest_path_infinite(int s, int t){ d[s] = 0; for(int i = 0; i < 2*V-1; i++){ for(auto& e : es){ if(d[e.from] != inf && d[e.to] > d[e.from] + e.cost){ d[e.to] = d[e.from] + e.cost; if(i >= V-1){ if(e.to == t) return true; d[e.to] = -inf; } } } } return false; } };
最短経路と始点sからたどり着ける閉路を verify
AOJ : Single Source Shortest Path (Negative Edges)
提出コード
すべての負の閉路の検出を verify
Atcoder : Asteroids2
提出コード
s, t 最短距離が非有界となるかの判定の verify
Atcoder: Coins Respawn
提出コード