ダイクストラ法（Dijkstra's Algorithm）の解説

一. 理論的基礎

ダイクストラ法（以下、DJアルゴリズム）の理論的基礎は、一つの単純な定理に基づいています：

次の最短経路は、アーク(V0, Vx)であるか、あるいは中間でSに含まれるいくつかの頂点を経由してVxに到達する経路である。（Sは最短経路が既知の頂点の集合である）

（定理を正確に記述するために、ここは直接引用しました。それが正しいかどうかについては、背理法で証明可能だそうです。）これは明らかに漸化式的なアルゴリズムです。次の経路を繰り返し求め、次がなくなるまで続けます。

二. 問題分析

次のような重み付き有向グラフがあるとします：

V0から出発して、他の各頂点までの最短経路を求めます。

まず、記述しやすい数学的形式に変換するために、対応する隣接行列を書きます（xは到達不能を表します）：

0	50	10	x	45	x
x	0	15	x	10	x
20	x	0	15	x	x
x	20	x	0	35	x
x	x	x	30	0	x
x	x	x	3	x	0

定理を分析すると、現時点でS集合には頂点V0のみが含まれています（V0自身への経路は間違いなく最短です）。S集合という補助空間以外に、以下のものが必要です：

• V集合：最短経路が未知の頂点で構成される集合。すなわちS集合の補集合。
• path[]：最短経路を記録し、結果を表示するために使用。
• dist[]：経路の長さを記録。用途は上記と同様。
• Vx：次の頂点を記録。

準備が整ったので、解法を開始します。

三. 解法プロセス

0. 初期状態

dist[]をV0から各頂点への直接距離で初期化し（xは直通不能）、path[]を対応する経路で初期化します。直通不能なものはNULLとします。V集合の中でdist値が最小の頂点V2を次の頂点（定理におけるVx）として選択します。

1. ステップ1

V2をS集合に加えます。中継点V2が増えたので、dist[]を更新します。V2を経由したほうが短くなるかどうかを確認し、計算結果に基づいてdist[]とpath[]を更新します。より短い経路の長さと対応する経路を格納します。V集合の中でdist値が最小のV3を次の頂点とします。

2. ステップ2-5

V集合に選択可能な頂点がなくなるまで、次の頂点の選択を続けます。

四. まとめ

DJアルゴリズムのプロセスは非常に単純です：

1. Sにおける最初の点（すなわち始点V0）を決定する。
2. 定理に基づいて漸化的に進める（常に最短を探し、その最短を経由した中継を試みる）。

アルゴリズムの考え方自体は難しくありません。当初理解できなかったのは、具体的な擬似コードの実装に振り回されていたからです。アルゴリズムを学ぶ際は、具体的な実装ではなく考え方に注目すべきです。特に擬似コードによるアルゴリズムでは、なぜその補助空間が必要なのかを説明せずに、奇妙なデータ構造を勝手に宣言することがよくあります。例えば本例では、S集合とV集合はどちらか一方あれば十分ですし、path[]とdist[]も構造体を使って明確に表現できます。しかし、擬似コードではあちこちに散らばって使われており、過剰な補助空間がかえってアルゴリズム自体の理解を妨げていました。