ei1333's page

単一始点最短路(SPFA)

説明

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

使い方

• shortest_path_faster_algorithm(g, s): 重み付き有向グラフ $g$ 上で, 頂点 $s$ からすべての頂点への最短距離を求め, その列を返す。負閉路が検出された時空列を返す。

計算量

$O(VE)$

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

実装例

問題例

• 検証済AOJ GPL_1_B 単一始点最短経路（負の重みをもつ辺を含む）