単一始点（終点）最短路（Dijkstra法） - アルゴリズムとデータ構造大全

単一始点最短路（Dijkstra法） 重みが全て\(0\)以上である任意の重み付きグラフ\(G\)における単一始点最短路は，Dijkstra法によって\(O(|E| \log |V|)\)で求めることができる． 単一始点最短路とは，あるノード\(s \in G\)から，\(G\)に含まれる任意のノードまでの最短路である．以降始点を\(s\)と呼ぶ． 説明 以下では，あるノード\(i\)について，\(s\)から\(i\)までの最短路長を\(d_{s→i}\)とする．また，あるノード\(i\)から出てあるノード\(j\)に入る(有向)辺の重みを\(e_{i→j}\)とする． 前提条件から全ての辺の重みが\(0\)以上であるため，\(s\)から到達可能な任意の\(y\)について以下の式が成り立つ． $$d_{s→y} = min(d_{s→x} + e_{x→y}) \quad ただし \qua