SPFA

keyword:

overview

shortest path faster algorithm 負閉路検出可能・負辺動作可能。 ベルマンフォードより速いらしい。 ただし閉路検出が遅いような気がする。

usage

vector<DGraphE::W_T> shortestPathFasterAlgorithm(const DGraphE& graph, int start = 0, bool* detectNegativeCycle = nullptr)
detectNegativeCycle = nullptrと置くと負閉路検出を無効化する

verified

https://atcoder.jp/contests/abc137/submissions/7173578

references

http://hogloid.hatenablog.com/entry/20120409/1333973448
https://tubo28.me/compprog/algorithm/spfa/

require

#include <vector>
#include <queue>
#include <limits>
using namespace std;
#include "src/cpp/graph/datastructure/dgraphe.cpp"

code

last commit

[e98740a0](2019-09-23 21:02) Apply update and refactor (#46)