最短経路問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/02/22 08:34 UTC 版)
グラフ理論における最短経路問題（さいたんけいろもんだい、英: shortest path problem）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。
種類
- 2頂点対最短経路問題
- 特定の2つのノード間の最短経路問題。一般的に単一始点最短経路問題のアルゴリズムを使用する。
- 単一始点最短経路問題 (SSSP：Single Source Shortest Path)
- 特定の1つのノードから他の全ノードとの間の最短経路問題。この問題を解くアルゴリズムとしては、ダイクストラ法やベルマン-フォード法がよく知られている。
- 全点対最短経路問題 (APSP : All Pair Shortest Path)
- グラフ内のあらゆる2ノードの組み合わせについての最短経路問題。この問題を解くアルゴリズムとしては、ワーシャル-フロイド法が知られている。
このような分類がされているのは、後者の問題が単に前者の問題を初期条件（ノード）を変えて繰り返し解くのではなく、アルゴリズムの過程で得た情報を利用して計算量を減らすことが可能となるからでもある。
単一始点最短経路問題
辺の重みなし有向グラフ
| アルゴリズム | 計算量 | 作者 | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 幅優先探索 |  | ||||||||||
| 非線形(制約付き) |
| ||||||||||
| 凸最適化 |
| ||||||||||
| 組合せ最適化 |
| ||||||||||
| メタヒューリスティクス | |||||||||||
| 典拠管理データベース: 国立図書館 |
|---|
最短経路問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/16 12:19 UTC 版)
詳細は「最短経路問題」を参照 ある頂点から他の頂点への移動コストが最小になるような経路を求める問題を最短経路問題という。ある頂点から他の全ての頂点に移動するコストが最小になる木のことを最短経路木といい、これは全域木である。最短経路問題は単一の頂点から任意の頂点への最短経路木を求める方法としてはダイクストラ法やベルマン-フォード法などが、また任意の頂点から任意の頂点への移動コストが最小になるような最短経路木を求める方法としてはワーシャル-フロイド法が知られている。
※この「最短経路問題」の解説は、「全域木」の解説の一部です。
「最短経路問題」を含む「全域木」の記事については、「全域木」の概要を参照ください。
ウィキペディア小見出し辞書の「最短経路問題」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 最短経路問題のページへのリンク
