最短経路問題とは？さいたんけいろもんだい
最短経路問題とは、辺に重みが付いたグラフで、指定した2点を結ぶ経路のうち重みの合計が最小になるものを求める問題。ある1点からすべての点への距離を求める型と、全点対を求める型がある。通信経路の選択、配送計画、工程の所要時間の計算など、判断の対象が「経路」である問題に広く当てはまる。
最終更新：2026-10-06
ITサービスマネージャを最短で暗記・合格する →背景
経路の候補は分岐が増えると爆発的に増え、全部数え上げるやり方は現実の規模で破綻する。そこで、途中まで確定した最短距離を使い回して残りを絞り込むという手続きが考え出された。重要なのは、経由地の数ではなく重みの合計で優劣が決まる点で、この前提を共有していないと結果が直感と食い違って見える。
具体例
都市間の距離を重みとしたグラフで、A→B→Eが12、A→C→D→Eが10なら、経由地が多い後者が最短になる。ネットワークではOSPFがこの考え方で経路表を作っており、帯域の広い回線を経由するほうが遠回りでも選ばれる。運用ではこの性質を知らないと、「なぜ隣の拠点へ本社経由で流れているのか」という切り分けで足を止めることになる。
試験での引っ掛け
経由する点の数が少ないほど短い、という読み方が誤りで、判断は重みの合計で行う。辺の本数だけを最小にしたい場合は重みをすべて1と見なした探索になり、別の問題になる。また工程管理で出てくるクリティカルパスは、同じくグラフを扱うが最長の経路を求めるもので、目的が逆であることを取り違えやすい。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。