ei1333's page

ホーム > Wiki

単一始点最短路(Dijkstra)

説明

負辺のない単一始点全点間最短路を求めるアルゴリズム。負辺が無いと仮定すると、各地点でもっとも近いところから距離が確定していく。距離順でソートされたヒープを用いると、効率よく距離を確定していくことができる。

使い方

計算量

$O(E \log V)$

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

実装例

問題例

参考資料