単一始点最短路 (SPFA)
概要
単一始点最短経路問題を解くアルゴリズムです．閉路があっても大丈夫です．計算量的にはベルマンフォード (bellman-ford.cc) と同じです．しかし負辺が無ければ，まだ一度も見ていない頂点間 (どちらも距離が INF のまま) の更新や，すでに最短距離が確定した頂点をまた見に行くことが少ないので多少高速になることが見込まれます．
使い方
負のループも OK．始点から到達可能な負のループがあると second が false になる．
計算量
$O(VE)$ BFより速い．
実装
std::pair<std::vector<Weight>, bool> spfa(const Graph &g, int s) {
static const Weight INF = std::numeric_limits<Weight>::max() / 4;
const int n = g.size();
std::queue<int> q;
std::vector<Weight> dist(n, INF);
std::vector<int> inQ(n);
std::vector<int> count(n);
dist[s] = 0;
q.emplace(s);
inQ[s] = true;
++count[s];
bool negCycle = false;
while (q.size()) {
int v = q.front();
q.pop();
inQ[v] = false;
for (auto &e : g[v]) {
if (dist[v] != INF && dist[e.dst] > dist[v] + e.weight) {
dist[e.dst] = dist[v] + e.weight;
if (!inQ[e.dst]) {
q.emplace(e.dst);
inQ[e.dst] = true;
++count[e.dst];
if (count[e.dst] >= n) {
negCycle = true;
goto END;
}
}
}
}
}
END:;
return std::make_pair(dist, !negCycle);
}