ダイクストラ法

読み：だいくすとらほう　／　英語表記：Dijkstra's algorithm

ルーティング・冗長化
通信の基礎

グラフ上で、ある1つの頂点から他のすべての頂点への最短経路を求めるアルゴリズム。OSPFが経路の計算に使う。辺のコストが負でないことが前提。

イマシルちゃんの解説

ダイクストラ法は、一つの出発点から各地点までの最短経路を求めるアルゴリズムだよ。
道の長さや通信経路の負担を表すコストを足し合わせて比べるんだ。
まず出発点から始めて、そこから行ける地点までの合計コストを記録するよ。
未確定の地点のうち合計コストが最小の地点を確定し、そこを通る方が安ければ隣の地点の記録を更新するんだ。
これを繰り返すと、到達できる各地点への最短経路が決まるよ。
各区間のコストが負でない場合に使える計算で、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)である

実際の試験ではここに出る！全10問

ネットワークスペシャリスト

午前Ⅱ

午後Ⅱ

R6春問1

テクニカルエンジニア（ネットワーク）

午前

H20秋問32