グラフ理論における最短経路問題（さいたんけいろもんだい、）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。このような分類がされているのは、後者の問題が単に前者の問題を初期条件（ノード）を変えて繰り返し解くのではなく、アルゴリズムの過程で得た情報を利用して計算量を減らすことが可能となるからでもある。最短経路の距離は部分構造最適性が成立しており、下記漸化式が成立する。証明は『アルゴリズムイントロダクション』（ISBN 978-4764904088）などを参照。単一始点の場合 formula_9 なら幅優先探索が、formula_10 ならダイクストラ法が、そうでないならベルマン-フォード法が使える。辺の重みが非負値の2頂点対最短経路問題で、最短経路の距離の下限値が分かっている場合はA*を使うと、ダイクストラ法よりも速く求まる。最短経路問題の身近な応用例には、鉄道の経路案内（駅すぱあと、駅探、NAVITIMEなど）がある。駅をノードとし、駅と駅の所要時間を重みとしたエッジとして、鉄道線路をグラフ化して最短経路を求めている。最短経路とは逆の問題で、最長単純道問題もあるが、最短経路の場合は、最短経路の部分問題もやはり最短経路であるが、最長単純道の場合、部分構造最適性が成立していなく、貪欲法などで解くことが出来なく、辺の重みなしであっても、NP完全問題である。

出典:wikipedia