最短経路問題とは？さいたんけいろもんだい
最短経路問題とは、重み付きグラフで、指定した2頂点を結ぶ経路のうち重みの合計が最小になるものを求める問題。始点1つからの最短距離を求める型と全頂点対を求める型がある。リンクの帯域から算出したコストを重みと見れば、OSPFが各ルータで解いているのはこの問題そのものである。
最終更新：2026-10-06
ネットワークSPを最短で暗記・合格する →背景
経路が複数ある網でどれを使うかを人が決めていては、リンクが1本落ちるたびに全機器の設定を書き換えることになる。「重みの合計が最小」という機械的に判定できる基準を置けば、同じ地図を持つ全ルータが同じ答えに行き着き、故障時も自律的に選び直せる。ダイクストラ法を使うリンクステート型のルーティングはこの考え方の実装で、計算量はそのまま収束時間とCPU負荷の議論になる。
具体例
OSPFは各ルータがLSAで集めた同一のリンクステートデータベースから、自分を始点とする最短経路木をダイクストラ法で求める。帯域が広いほどコストが小さくなるよう設計するため、経由ルータが多くても広帯域を通る経路が選ばれることがあり、地図上の見た目の近さとは一致しない。
試験での引っ掛け
「経由する頂点が少ない＝最短」ではなく、判定は重みの合計で行う。辺の数だけを最小にしたい場合は全ての重みを1と見なした幅優先探索になり、これはホップ数で選ぶ距離ベクトル型の考え方に近い。また工程管理のクリティカルパスは合計が最大になる経路を求めるもので、同じ経路探索でも目的が逆である。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。