ダイクストラ法ほうの基本きほん

date2026-07-14document_iddoc_68ebd8de946186fb80b167dcbafb01e5descriptionダイクストラ法を、非負重み、暫定距離、確定済み集合、緩和、不変条件、優先度付きキューの観点から説明する。prerequisites最短路の基本 / グラフの基本 / 計算量の基本 / ヒープと木構造type講義statusactive

algorithmgraphundergraduatelecture

1導入どうにゅう

この講義こうぎでは、辺へんの重おもみが非負ひふであるグラフについて、ダイクストラ法ほうが単一始点最短距離たんいつしてんさいたんきょりを計算けいさんする方法ほうほうと、その正当性せいとうせいを説明せつめいする。暫定距離ざんていきょり、確定済かくていずみ頂点ちょうてん、緩和かんわを定義ていぎし、不変条件ふへんじょうけんとカット論法ろんぽうによって証明しょうめいする。

2問題設定もんだいせってい

有限ゆうげんの有向ゆうこうまたは無向むこうグラフ $G = (V, E)$ 、始点してん $s \in V$ 、重おもみ関数かんすう $w : E \to R_{[PARSE ERROR: Undefined("Command(\"ge\")")] 0}$ を考かんがえる。道みちの長ながさを、その辺へんの重おもみの総和そうわとする。 $s$ から $v$ への最短距離さいたんきょりを $δ (s, v)$ と表あらわし、到達不能とうたつふのうなら $δ (s, v) = \infty$ とする。

data/lecture/information/algorithm/graph/shortest-path-basics.lecture.n.md

3用語ようご

暫定距離ざんていきょり $d [v]$ は、すでに発見はっけんした $s$ から $v$ への道みちのうち最小さいしょうの長ながさである。未発見みはっけんなら $\infty$ とする。したがって、常つねに $δ (s, v) [PARSE ERROR: Undefined("Command(\"le\")")] d [v]$ が成立せいりつする。
確定済かくていずみ集合しゅうごう $S$ は、 $d [v] = δ (s, v)$ であることを証明済しょうめいずみの頂点ちょうてんの集合しゅうごうである。この状態じょうたいを $v$ が 確定かくていした という。
緩和かんわ とは、辺へん $(u, v)$ に対たいして $d [u] + w (u, v) < d [v]$ なら、 $d [v] \leftarrow d [u] + w (u, v)$ と更新こうしんする操作そうさである。
優先度付ゆうせんどつきキュー は、未確定みかくていの候補こうほから $d$ が最小さいしょうの頂点ちょうてんを取とり出だすデータ構造こうぞうである。

4アルゴリズム

まず $d [s] = 0$ 、 $v \neq s$ に対たいして $d [v] = \infty$ 、 $S = [PARSE ERROR: Undefined("Command(\"varnothing\")")]$ とする。優先度付ゆうせんどつきキューには $(0, s)$ を挿入そうにゅうする。その後ご、キューが空からになるまで次つぎを反復はんぷくする。

距離値きょりちが最小さいしょうの組くみ $(x, u)$ を取とり出だす。
$u \in S$ または $x \neq d [u]$ なら、この古ふるい組くみを無視むしする。
それ以外いがいでは $u$ を $S$ に加くわえ、 $u$ から出でる各辺かくへん $(u, v)$ のうち $v \notin S$ であるものを緩和かんわする。 $d [v]$ が減少げんしょうしたら、新あたらしい $(d [v], v)$ をキューに挿入そうにゅうする。

同おなじ頂点ちょうてんの古ふるい距離値きょりちがキューに残のこる実装じっそうでは、このような要素ようそを stale entry とよぶ。2 の検査けんさにより、decrease-key 操作そうさをもたないヒープでも正ただしく実装じっそうできる。

5不変条件ふへんじょうけん

各反復かくはんぷくの開始時かいしじに、次つぎが成立せいりつする。

$u \in S$ なら $d [u] = δ (s, u)$ である。
$v \notin S$ の $d [v]$ は、 $s$ から $v$ への道みちで、 $v$ 以外いがいの頂点ちょうてんが $S$ に属ぞくするものの最小長さいしょうちょうである。 $v \neq s$ では、内部頂点ないぶちょうてんが $S$ に属ぞくし、最後さいごの辺へんが $S$ から $v$ へ進すすむ候補こうほと同値どうちである。そのような道みちがなければ $d [v] = \infty$ である。

初期状態しょきじょうたいでは、 $s$ への長ながさ 0 の道みちだけが候補こうほなので、この条件じょうけんが成立せいりつする。確定かくていした $u$ から出でる辺へんをすべて緩和かんわすると、 $S$ を内部ないぶに使用しようして新あらたに到達とうたつできる候補こうほが過不足かぶそくなく反映はんえいされる。したがって 2 は保存ほぞんされる。

6確定操作かくていそうさの正当性せいとうせい

$S$ の外部がいぶで $d$ が最小さいしょうの頂点ちょうてんを $u$ とする。 $u = s$ なら $d [s] = 0 = δ (s, s)$ である。 $u \neq s$ が始点してんから到達可能とうたつかのうであるとき、 $s$ から $u$ への最短路さいたんろ $P$ を一ひとつ選えらぶ。 $P$ が $S$ から $V ∖ S$ へ最初さいしょに出でる辺へんを $(y, z)$ とする。この境界きょうかいを横断おうだんする議論ぎろんを カット論法ろんぽう という。

$P$ の $s$ から $y$ までの接頭部分せっとうぶぶんの長ながさを $c (P [s : y])$ とする。 $y \in S$ なので、不変条件ふへんじょうけんと $(y, z)$ の緩和かんわから

d [z] [PARSE ERROR: Undefined("Command(\"le\")")] δ (s, y) + w (y, z) [PARSE ERROR: Undefined("Command(\"le\")")] c (P [s : y]) + w (y, z) .

重おもみがすべて非負ひふであるため、 $P$ の $z$ 以降いこうを加くわえても長ながさは減少げんしょうせず、

c (P [s : y]) + w (y, z) [PARSE ERROR: Undefined("Command(\"le\")")] c (P) = δ (s, u)

が成立せいりつする。また $u$ の選択せんたくから $d [u] [PARSE ERROR: Undefined("Command(\"le\")")] d [z]$ であり、暫定距離ざんていきょりは実在じつざいする道みちの長ながさなので $δ (s, u) [PARSE ERROR: Undefined("Command(\"le\")")] d [u]$ である。したがって、

δ (s, u) [PARSE ERROR: Undefined("Command(\"le\")")] d [u] [PARSE ERROR: Undefined("Command(\"le\")")] d [z] [PARSE ERROR: Undefined("Command(\"le\")")] δ (s, u)

となり、 $d [u] = δ (s, u)$ を得える。ゆえに $u$ を確定かくていしても不変条件ふへんじょうけん 1 は保存ほぞんされる。

7到達不能とうたつふのうな頂点ちょうてん

キューが空からになったとき、 $s$ から到達可能とうたつかのうな頂点ちょうてんはすべて確定済かくていずみである。到達不能とうたつふのうな頂点ちょうてんはキューへ挿入そうにゅうされず、 $d [v] = \infty$ のまま残のこる。無限大むげんだいの候補こうほを取とり出だして確定かくていする必要ひつようはない。

8負辺ふへんを許ゆるせない理由りゆう

$s \to u$ の重おもみを 2、 $s \to v$ を 5、 $v \to u$ を -4 とする。ダイクストラ法ほうは $d [u] = 2$ を $d [v] = 5$ より先さきに確定かくていする。しかし、 $s \to v \to u$ の長ながさは 1 であり、真しんの最短距離さいたんきょりは $δ (s, u) = 1$ である。負辺ふへんによってカットを横断おうだんした後あとに道みちの長ながさが減少げんしょうするため、証明しょうめいの非負性ひふせいを使用しようした不等式ふとうしきが破綻はたんする。

9計算量けいさんりょう

隣接りんせつリストと二分にぶんヒープを使用しようすると、有向辺ゆうこうへんは高々一度たかだかいちど緩和かんわされる。無向辺むこうへんは両端りょうたんの隣接りんせつリストに現あらわれるため、各方向かくほうこうから高々一度たかだかいちどずつ調査ちょうさされる。成功せいこうした緩和かんわごとに高々たかだか 1 個この組くみを挿入そうにゅうする。したがって、時間計算量じかんけいさんりょうは

O ((| V | + | E |) \log | V |)

であり、始点してんからすべての頂点ちょうてんへ到達可能とうたつかのうなら $O (| E | \log | V |)$ と表記ひょうきできる。stale entry を保持ほじする実装じっそうの補助空間ほじょくうかんは $O (| V | + | E |)$ である。decrease-key を使用しようする実装じっそうでは、キューの要素数ようそすうを $O (| V |)$ に抑おさえられる。

10要点ようてん

ダイクストラ法ほうの前提ぜんていは、すべての辺重へんじゅうみが非負ひふであることである。
最小さいしょうの暫定距離ざんていきょりをもつ頂点ちょうてんを確定かくていできる根拠こんきょは、不変条件ふへんじょうけんとカット論法ろんぽうにある。
stale entry、到達不能とうたつふのうな頂点ちょうてん、使用しようするヒープの操作そうさを実装仕様じっそうしようとして明示めいじする。

Dijkstra's Algorithm

1Introduction

This lecture explains how Dijkstra's algorithm computes single-source shortest-path distances in a graph with nonnegative edge weights. It defines tentative distances, settled vertices, and relaxation, then proves correctness through a loop invariant and a cut argument.

2Problem setting

Let $G = (V, E)$ be a finite directed or undirected graph, let $s \in V$ be the source, and let $w : E \to R_{[PARSE ERROR: Undefined("Command(\"ge\")")] 0}$ be the weight function. The length of a path is the sum of its edge weights. Write $δ (s, v)$ for the shortest-path distance from $s$ to $v$ , with $δ (s, v) = \infty$ when $v$ is unreachable from $s$ .

data/lecture/information/algorithm/graph/shortest-path-basics.lecture.n.md

3Terminology

The tentative distance $d [v]$ is the minimum length among the currently discovered paths from $s$ to $v$ . It is $\infty$ if no such path has been discovered. Consequently, $δ (s, v) [PARSE ERROR: Undefined("Command(\"le\")")] d [v]$ always holds.
The settled set $S$ consists of vertices for which $d [v] = δ (s, v)$ has been proved. Such a vertex is called settled.
To relax an edge $(u, v)$ is to assign $d [v] \leftarrow d [u] + w (u, v)$ whenever $d [u] + w (u, v) < d [v]$ .
A priority queue extracts a vertex with minimum $d$ among unsettled candidates.

4Algorithm

Initialize $d [s] = 0$ , $d [v] = \infty$ for $v \neq s$ , and $S = [PARSE ERROR: Undefined("Command(\"varnothing\")")]$ . Insert $(0, s)$ into a priority queue. Repeat the following steps until the queue is empty.

Extract a pair $(x, u)$ with minimum distance key.
If $u \in S$ or $x \neq d [u]$ , discard this obsolete pair.
Otherwise, add $u$ to $S$ and relax every outgoing edge $(u, v)$ for which $v \notin S$ . Whenever $d [v]$ decreases, insert the new pair $(d [v], v)$ .

An implementation that leaves old distance keys in the queue can contain several entries for one vertex. Such an obsolete pair is a stale entry. The test in step 2 permits a correct heap implementation without a decrease-key operation.

5Loop invariant

At the beginning of every iteration, the following statements hold.

For every $u \in S$ , $d [u] = δ (s, u)$ .
For every $v \notin S$ , $d [v]$ is the minimum length of an $s$ -to- $v$ path whose vertices other than $v$ belong to $S$ . When $v \neq s$ , this is equivalent to requiring that its internal vertices lie in $S$ and its final edge cross from $S$ to $v$ . If no such path exists, then $d [v] = \infty$ .

Initially, only the length-zero path to $s$ is a candidate, so the invariant holds. Relaxing every outgoing edge of a newly settled vertex records exactly the new candidate paths made available by using vertices of $S$ internally. Hence statement 2 is preserved.

6Correctness of settling

Let $u$ be an unsettled vertex with minimum $d$ . If $u = s$ , then $d [s] = 0 = δ (s, s)$ . Otherwise, suppose that $u$ is reachable, and choose a shortest path $P$ from $s$ to $u$ . Let $(y, z)$ be the first edge of $P$ that leaves $S$ . Reasoning across this boundary is the cut argument.

Let $c (P [s : y])$ denote the length of the prefix of $P$ from $s$ to $y$ . Because $y \in S$ , the invariant and the relaxation of $(y, z)$ imply

d [z] [PARSE ERROR: Undefined("Command(\"le\")")] δ (s, y) + w (y, z) [PARSE ERROR: Undefined("Command(\"le\")")] c (P [s : y]) + w (y, z) .

All edge weights are nonnegative, so adding the suffix of $P$ after $z$ cannot decrease its length. Thus

c (P [s : y]) + w (y, z) [PARSE ERROR: Undefined("Command(\"le\")")] c (P) = δ (s, u) .

The choice of $u$ gives $d [u] [PARSE ERROR: Undefined("Command(\"le\")")] d [z]$ , while a tentative distance is the length of an actual path and therefore $δ (s, u) [PARSE ERROR: Undefined("Command(\"le\")")] d [u]$ . Consequently,

δ (s, u) [PARSE ERROR: Undefined("Command(\"le\")")] d [u] [PARSE ERROR: Undefined("Command(\"le\")")] d [z] [PARSE ERROR: Undefined("Command(\"le\")")] δ (s, u),

which proves $d [u] = δ (s, u)$ . Settling $u$ therefore preserves statement 1 of the invariant.

7Unreachable vertices

When the queue becomes empty, every vertex reachable from $s$ has been settled. An unreachable vertex is never inserted, so its value remains $d [v] = \infty$ . There is no need to extract or settle candidates whose keys are infinite.

8Why negative edges are forbidden

Consider edges $s \to u$ of weight 2, $s \to v$ of weight 5, and $v \to u$ of weight -4. Dijkstra's algorithm settles $u$ with $d [u] = 2$ before $v$ with $d [v] = 5$ . However, the path $s \to v \to u$ has length 1, so the true distance is $δ (s, u) = 1$ . A negative edge can decrease a path length after the path crosses the cut, invalidating the inequality in the proof that depends on nonnegativity.

9Complexity

With adjacency lists and a binary heap, each directed edge is relaxed at most once. An undirected edge occurs in the adjacency lists of both endpoints and is examined at most once in each direction. Each successful relaxation inserts at most one pair. The running time is

O ((| V | + | E |) \log | V |),

which is commonly written as $O (| E | \log | V |)$ when every vertex is reachable from the source. An implementation that retains stale entries uses $O (| V | + | E |)$ auxiliary space. An implementation with decrease-key can keep the queue size at $O (| V |)$ .

10Summary

Dijkstra's algorithm requires every edge weight to be nonnegative.
The loop invariant and cut argument justify settling a vertex with minimum tentative distance.
Stale entries, unreachable vertices, and the supported heap operations must be stated as part of the implementation contract.