最短経路問題とは？さいたんけいろもんだい
最短経路問題とは、重み付きグラフで、指定した2頂点を結ぶ経路のうち重みの合計が最小になるものを求める問題。カーナビの経路探索、通信経路の選択、工程の所要日数計算などに応用される。始点1つからの最短距離を求める型と、全頂点対を求める型がある。
最終更新：2026-10-06
情報処理安全確保支援士を最短で暗記・合格する →具体例
都市間の距離を重みとしたグラフで、AからEへの経路が「A-B-E＝12」と「A-C-D-E＝10」なら後者が最短となる。経由地が増えても合計が小さければそちらが選ばれる点が、直感と食い違いやすい。
試験での引っ掛け
「経由する頂点の数が少ない＝最短」ではなく、重みの合計で判断する。辺の数だけを最小にしたい場合は重みを全て1と見なした幅優先探索になる。また最長経路（クリティカルパス）を求める工程管理の問題とは目的が異なる。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。