ダイクストラ法
グラフ上で、ある1つの頂点から他のすべての頂点への最短経路を求めるアルゴリズム。OSPFが経路の計算に使う。辺のコストが負でないことが前提。
イマシルちゃんの解説
スタート地点から、いろんな場所までの一番近い道を全部調べたいとき、どうする？
ダイクストラ法では、まず「スタートから一番近い場所」を確定させるんだ。
次に、確定した場所から行けるところの距離を更新して、また「一番近い場所」を確定させる。
これを繰り返していくと、近い順に、すべての場所への最短の道が決まっていくんだよ！
より深い解説
定義
ダイクストラ法は、1959年にエドガー・ダイクストラが発表した、単一始点最短経路問題を解くアルゴリズムである。重み（コスト）付きのグラフで、始点からほかのすべての頂点までの最短距離と、その経路を求める。結果として得られる、始点を根とした木を最短経路木という。
手順
- 始点の距離を0、ほかのすべての頂点の距離を∞とする。すべての頂点を「未確定」とする
- 未確定の頂点のうち、距離が最小のものを選び、「確定」にする
- 確定した頂点から辺でつながる未確定の頂点について、「確定した頂点の距離 + 辺のコスト」が今の距離より小さければ、距離を更新し、どの頂点から来たか（直前の頂点）を記録する
- すべての頂点が確定するまで、2と3を繰り返す
各頂点の「直前の頂点」をたどると、最短経路がわかる。
計算例
次のようなネットワークで、Pを始点とする（括弧内はコスト）。
P─Q (2) P─R (5) Q─R (1) Q─S (4) R─S (1)| 手順 | 確定する頂点 | P | Q | R | S |
|---|---|---|---|---|---|
| 初期 | − | 0 | ∞ | ∞ | ∞ |
| 1 | P | 0 | 2（P） | 5（P） | ∞ |
| 2 | Q | 2 | 3（Q） | 6（Q） | |
| 3 | R | 3 | 4（R） | ||
| 4 | S | 4 |
最短経路木の辺は、P─Q、Q─R、R─Sになる。P─R（コスト5）は、Qを経由したほうが安い（2＋1＝3）ため、木には入らない。
OSPFでの使い方
OSPFのルータは、LSDB（ネットワークの地図）をもとに、自分自身を始点としてダイクストラ法を実行し、最短経路木を作る。この木から、宛先ネットワークごとに「最初にどの隣接ルータへ送ればよいか」（ネクストホップ）を取り出して、経路表を作る。OSPFでは、この計算をSPF計算（Shortest Path Firstの計算）と呼ぶ。
スパニングツリーとの関係
スパニングツリープロトコル（STP）は、ルートブリッジから各ブリッジへのルートパスコストが最小になるようにポートを選ぶ。結果としてできる木は、ルートブリッジを始点とした最短経路木と同じ考え方で求められる。グラフの問題として「ルートからの最短経路」を考えれば、手作業でもスパニングツリーを求められる。
なお、木に含まれる辺のコストの合計が最小になるように選ぶ最小全域木（クラスカル法やプリム法で求める）とは、目的が異なる。最短経路木は「根から各頂点までの距離」を、最小全域木は「木全体の辺の合計」を最小にする。
前提と計算量
- 辺のコストが負の場合は、正しい結果が得られない（その場合はベルマンフォード法を使う）
- 頂点の数をV、辺の数をEとすると、優先度付きキュー（ヒープ）を使った実装の計算量はO((V + E) log V)である
実際の試験ではここに出る！
- ネットワークスペシャリスト 令和6年度 春期 午前Ⅱ 問4
- ネットワークスペシャリスト 令和6年度 春期 午前Ⅱ 問5
- ネットワークスペシャリスト 令和5年度 春期 午前Ⅱ 問4
- ネットワークスペシャリスト 令和元年度 秋期 午前Ⅱ 問2