グラフ理論における最短経路問題はノード（開始点）からあるパス（経路）を通りノード（終点）への、パスに付随する重みが 最小の経路を求める最適化問題です。 解くためのアルゴリズムである「ダイクストラ法」・等がありますが、ここでは全ての経路を計算して解を求めます。
結果表示（ ）
例１でノードを駅、パスを路線、重みを運賃だとして、駅Aから駅Hへは最低いくら必要か という問題です。全ての経路をたどってみて一番短いものを選べば、 ノードAからノードHに向かう経路は同じノードを2回通らないという決まりだけで 列挙すると40通りで、最短路線は⇒AD(2)⇒DE(5)⇒EF(2)⇒FH(3)で運賃は１２です。