最短経路問題
出典: フリー百科事典『ウィキペディア（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ノードの組み合わせについての最短経路問題。この問題を解くアルゴリズムとしては、ワーシャル-フロイド法が知られている。
このような分類がされているのは、後者の問題が単に前者の問題を初期条件（ノード）を変えて繰り返し解くのではなく、アルゴリズムの過程で得た情報を利用して計算量を減らすことが可能となるからでもある。
単一始点最短経路問題
辺の重みなし有向グラフ
| アルゴリズム | 計算量 | 作者 | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 幅優先探索 |  | ||||||||||
| 非線形(制約付き) |
| ||||||||||
| 凸最適化 |
| ||||||||||
| 組合せ最適化 |
| ||||||||||
| メタヒューリスティクス | |||||||||||
| 典拠管理データベース: 国立図書館 |
|---|
このページでは「ウィキペディア」から最短経路問題を検索した結果を表示しています。
Weblioに収録されているすべての辞書から最短経路問題を検索する場合は、下記のリンクをクリックしてください。
全ての辞書から最短経路問題
を検索
Weblioに収録されているすべての辞書から最短経路問題を検索する場合は、下記のリンクをクリックしてください。
全ての辞書から最短経路問題
を検索
- 最短経路問題のページへのリンク
