最短路問題

【さいたんろもんだい (shortest path problem)】

有向グラフの各枝に長さが付与されたネットワークにおいて, 指定された2点間の有向道の中で最短の長さをもつもの(最短路)を見出す組合せ最適化問題. ナップサック問題, PERT等様々な問題が最短路問題とも関係し, さらに, ネットワークフロー問題や配送計画等のより複雑な問題の子問題として出現することも多い. ダイクストラ法やベルマン・フォード法等を用いて解くことができる. 無向グラフに対しても同様に定義される.