最短経路問題とは？さいたんけいろもんだい
最短経路問題は、辺に重みの付いたグラフで、指定した2点を結ぶ経路のうち重みの合計が最小のものを求める問題である。判断の基準は経由する点の数ではなく重みの総和で、始点1つから全点への距離を求める型と、全点対を求める型に分かれる。
最終更新：2026-10-07
高度試験の午前Iを最短で暗記する →背景
距離・所要時間・通信コスト・料金といった別々の指標が、いずれも「辺に付いた数の合計を最小にする」という同じ形に還元できる。この抽象化のおかげで、経路探索の道具を一度作れば分野を越えて使い回せる。だから基礎理論として繰り返し出題される。
具体例
ダイクストラ法は始点に近い点から順に確定させて広げる方法で、カーナビの経路探索やOSPF（リンク状態型のルーティングプロトコル）の経路計算に使われる。A地点からE地点へ、A-B-Eが合計12、A-C-D-Eが合計10なら、経由地の多い後者が最短になる。
試験での引っ掛け
「経由する点が少ない＝最短」ではない。辺の本数だけを最小にしたい場合は、すべての重みを1とみなした幅優先探索になる。またダイクストラ法は負の重みがあると正しく動かない。工程管理のクリティカルパスは最長経路を求めるもので、目的が逆である。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。