ダイクストラ法
u {\displaystyle u} を H {\displaystyle H} に追加した結果「 H ∪ v {\displaystyle H\cup {v}} 内での s {\displaystyle s} から v {\displaystyle v} への最短距離」である d ( v ) {\displaystyle d(v)} が変化するのは、 u {\displaystyle u} と v {\displaystyle v} とを結ぶ辺がある場合に限られる。
u {\displaystyle u} を H {\displaystyle H} に追加後の「 H ∪ v {\displaystyle H\cup {v}} 内での s {\displaystyle s} から v {\displaystyle v} への最短距離」は次のいずれかと一致する。
(a) u {\displaystyle u} を H {\displaystyle H} に追加する前の段階での s {\displaystyle s} から v {\displaystyle v} への最短経路
(b) u {\displaystyle u} を H {\displaystyle H} に追加する前の段階での s {\displaystyle s} から u {\displaystyle u} への最短経路を通った後で u {\displaystyle u} と v {\displaystyle v} を結ぶ辺を通るという経路