最短経路問題とは？さいたんけいろもんだい
最短経路問題とは、地点を点、地点どうしのつながりを線で表し、線に距離や所要時間などの重みを付けた図（重み付きグラフ）で、指定した2点を結ぶ経路のうち重みの合計が最小になるものを求める問題。カーナビの経路探索、通信経路の選択、工程の日数計算などに使われ、代表的な解き方にダイクストラ法がある。
最終更新：2026-10-09
基本情報を最短で暗記・合格する →背景
「近い」を何で測るかは場面ごとに違う。距離が短くても渋滞していれば時間はかかるし、通信なら回線の速さや混み具合が効く。測りたいものを線の重みとして数値にしておけば、どの尺度でも同じ手順で最小の経路を求められる。この一般化のおかげで、地図・通信・工程管理という別々の分野の問題を1つのアルゴリズムで解けるようになった。
具体例
都市間の距離を重みにしたグラフで、AからEへ行くのに「A→B→E」の合計が12、「A→C→D→E」の合計が10であれば、通る都市の数が多くても後者が最短になる。カーナビが遠回りに見える道を案内することがあるのは、この計算の結果である。
試験での引っ掛け
「通る点の数が少ない＝最短」ではなく、判断するのは重みの合計である。すべての重みを1とみなして辺の本数だけを最小にする場合は、幅優先探索（出発点から近い順に、線を1本ずつ広げて点を訪ねていく探索）になる。また工程管理で最も長い経路を求めるクリティカルパスの問題は、探すものが最長で目的が逆になる点も混同しやすい。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。