3 Minutes NetWorking Supplement
No.03

3Minutes NetWorking Supplement

補講第3回Dijkstraのアルゴリズム

■ ついに登場

おねーさん

ほげたん、ほげたん。

ほげたん

な〜に、おね〜さん?

おねーさん

乗っ取ったわよ、この場所を

ほげたん

さすがだね、おね〜さん。もうパパさんなんか目じゃないね。
いずれは本家「3Minutes Networking」にも進出だ!!

おねーさん

それはどうかしら?

ほげたん

あらら。おね〜さん、クール。

おねーさん

まぁ、できる事とできない事があるってことよ。
でもね、「3Min Supplement」ぐらいは私達でやりたいわね。

ほげたん

そだね。

■ Dijkstra

おねーさん

さて、ほげたん。今日の話だけど。
いつもいつもネットワークの話というのもアレだから、関連はあるけどちょっと目先を変えた話をしましょう。

ほげたん

へ〜。な〜になに、おね〜さん?

おねーさん

今日は、「Dijkstraのアルゴリズム」の話をするわ。

ほげたん

え〜っと。「でぃじゃくすとら」って何?

おねーさん

……。

ほげたん

ディジャブ? でもあれは[Deja]だし…………って、イタイイタイッ!!

おねーさん

莫迦

ほげたん

やめてやめてとめて。痛い痛いっ。

おねーさん

「ダイクストラ」と読むのよ。

ほげたん

は〜。死ぬかと思った。
で、だいくすとら? 何それ。

おねーさん

人名よ。人の名前。エドガー・ダイクストラ
数学者。この人が考えたアルゴリズムだから、「ダイクストラのアルゴリズム」。

ほげたん

へ〜。

おねーさん

この人が考えたアルゴリズム「ダイクストラのアルゴリズム」は日本語で「最短経路決定アルゴリズム」と呼ばれているわ。ねぇ、ほげたん、最短経路を英語で言うと?

ほげたん

最短経路? もっとも短い経路。
もっとも短い[Shortest]、経路[Path]。

おねーさん

最短経路を優先して選ぶとすると?

ほげたん

もっとも短い[Shortest]、経路[Path]を、優先[First]して…。

おねーさん

頭文字を取って?

ほげたん

えす、ぴー、えふ……SPF!!

おねーさん

よくできました。SPFは「最短経路優先」の意味。
そう、つまりOSPFのSPFアルゴリズムそのものなのよ。

ほげたん

は〜。すごいや。ディジャクストラさんはOSPFの生みの親なんだ。

おねーさん

ダイクストラ。

ほげたん

そうそう。その人。

おねーさん

まったく。でも、「生みの親」ってのはちょっと大袈裟かも。
ダイクストラのアルゴリズムはOSPF、IS-ISのSPFアルゴリズムだけじゃなく他のいろいろな所で応用されているのよ。

ほげたん

最短経路の決定だもんね。カーナビとかで使えそうだね。

おねーさん

ともかく。ちょっと復習。
ルーティングプロトコルで使われているアルゴリズムを答えなさい。

ほげたん

え〜っと。

  • ディスタンスベクタ … ベルマンフォード [Bellman-Ford] アルゴリズム
  • リンクステート … SPF [Shortest Path First] アルゴリズム
  • 拡張ディスタンスベクタ … DUAL [Diffusing Update ALgorithm]
ほげたん

だよね。

おねーさん

はい。その通り。
じゃ、このダイクストラのアルゴリズムを説明しましょう。

■ Dijkstraのアルゴリズム

おねーさん

じゃ、アルゴリズムの説明行くわね。

  1. 始点を決定する
  2. すべての点において、始点からの距離として最大値を設定する
  3. 始点に接続されているすべての点において、始点からの距離を求める。
  4. 始点に接続されているすべての点の中で、最短の点を確定とする。
  5. 確定した点に接続されているすべての点において、始点からの距離を求める。
    1. 新しく計算された距離が現在の距離より短い場合、新しく計算された距離を始点からの距離とする。以前の経路は使用しないものとして切断する。
    2. そうでない場合、現在の距離を始点からの距離とする。さらにその経路を使用しないものとして切断する。
  6. 現時点で始点からの距離が最短の点を確定とする。
  7. すべての点が確定するまで、5〜6を繰り返す
おねーさん

こう。

ほげたん

わからん

おねーさん

それは何、ほげたん? 私の説明が悪いとでも言いたいわけ?

ほげたん

ままままままま、まさか。そんな恐ろしいことを考えるわけないじゃないか、おね〜さん。
えぇ。僕も命は惜しいですから。

おねーさん

ふ〜ん。

ほげたん

おね〜さん、できれば図解か何かしていただけると大変ありがたいのですが…。

おねーさん

そうね。じゃ、図解で。

[FigureSP03-01:Dijkstraのアルゴリズム]

ほげたん

なるほどだよ、おね〜さん。

おねーさん

Aをルータ。B〜Kをネットワークとみたてるでしょ。
で、こう回転させて、切断したパスを消して、木構造に見立てると…。

[FigureSP03-02:SPFツリー]

おねーさん

ほらっ、SPFツリー

ほげたん

は〜、これがOSPFのSPFツリー。

おねーさん

そういうこと。

ほげたん

すごいよ、おね〜さん。

おねーさん

ネットワークと関係あるけど、目先の違った話だったでしょ。

ほげたん

うん。アルゴリズムなんて知らないからさ。目新しい話だねっ。

おねーさん

じゃ、今日はこれでおしまい。
おね〜さんと、

ほげたん

ほげたんのっ!!

おねーさん

3分間ネットワーク、

ほげたん

サプリメントでした〜〜〜っ!!
まったね〜〜〜〜!!

エドガー・ダイクストラ
[Edsger Wybe Dijkstra]
1930〜2002。オランダ人。
「ダイクストラのアルゴリズム」やセマフォの考案、構造化プログラミングの提唱など、業績は多い。
ほげたんほげたんの今日のポイント
  • ダイクストラのアルゴリズムはOPSFで使われている「最短経路決定」アルゴリズム。

3 Minutes NetWorking Supplement No.03

管理人:aji-ssz(at)selene.is.dream.jp