最終更新日：2009/01/20 23:52:02
解答
b
解説
問題に与えられたネットワーク図よりリンクステートデータベースを作成する。
リンクステートデータベースとは、ネットワークの情報を、ルータ同士やルータとネットワークなどの間を辺で結んだグラフ（有向グラフ）構造で表現し、それを表形式にしたものである。
実際に作成してみると以下のようにできる。
リンクステートデータベースとは、ネットワークの情報を、ルータ同士やルータとネットワークなどの間を辺で結んだグラフ（有向グラフ）構造で表現し、それを表形式にしたものである。
実際に作成してみると以下のようにできる。
| to＼from | Z | A | B | C |
| Z | 6 | 3 | ||
| A | 3 | 1 | 1 | |
| B | 3 | 1 | ||
| C | 7 | 1 | 3 |
最短パスツリーの作成
最短パスツリーを作るときに使うアルゴリズムがダイクストラアルゴリズムで、「すべてのノードのなかでコストが最小のノードを確定し、そのノードから次のノードを加えていく」作業を繰り返せば良い。
初め、起点がZであることからZを書き、リンクステートデータベースから、次のノードを追加する。この場合、次のノードはAとCであるからそれを加える。
コストを比べてみるとAが最小であることがわかりAの最小パスコストが決定する
Z→A：3
Z→C：7
コストを比べてみるとAが最小であることがわかりAの最小パスコストが決定する
Z→A：3
Z→C：7
決定したAから同様に、次のノードを追加する。この場合、次のノードはBとCであるからそれを加える。
コストを比べてみるとCが最小であることがわかりCの最小パスコストが決定する
Z→C：7
Z→A→B：6
Z→A→C：4
コストを比べてみるとCが最小であることがわかりCの最小パスコストが決定する
Z→C：7
Z→A→B：6
Z→A→C：4
決定したCから同様に、次のノードを追加する。この場合、次のノードはBであるからそれを加える。
これで、残りBの最小パスコストが決定する
Z→A→B：6
Z→A→C→B：5
これで、残りBの最小パスコストが決定する
Z→A→B：6
Z→A→C→B：5
解答はコストが確定していく順番を答えるので、ルータA→ルータC→ルータBの順ということになる。
答えを出すだけなら、最初の2ノードが分かった時点で正解がわかる。
答えを出すだけなら、最初の2ノードが分かった時点で正解がわかる。
関連項目
関連問題
参考文献・WEBページ
とこトンやさしいIPルーティング(SOFTBANK)
