ei1333's page

ホーム > Wiki

単一始点最短路(SPFA)

説明

単一始点全点間最短路を求めるアルゴリズム。負辺があっても動作する。また負閉路も検出する。Bellman-Ford よりもはやいらしい。

使い方

計算量

$O(VE)$

$V$: 頂点数, $E$: 辺数

実装例

問題例