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