SPFアルゴリズムの最短経路

テクニカルエンジニア（ネットワーク）平成20年度秋期午前問32

図のようなネットワークで，SPFアルゴリズムを使ってノード①からノード⑥への最適経路を計算したときの経路はどれか。ここで，図中の数字はコストを表す。

方向別コスト：①→②=5、②→①=3、①→③=3、③→①=2、②→③=4、③→②=1、②→④=5、④→②=4、②→⑤=1、⑤→②=2、③→⑤=6、⑤→③=5、④→⑤=2、⑤→④=1、④→⑥=2、⑥→④=3、⑤→⑥=4、⑥→⑤=2。

ア　①－②－④－⑥

イ　①－②－⑤－④－⑥

ウ　①－③－②－⑤－④－⑥

エ　①－③－⑤－④－⑥

図表を、内容・対応関係を保ったテキストに変換。原図は出典PDFを参照。

正解を表示

ウ

この問題に出てくる用語

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