|
グラフ理論における最短経路問題（さいたんけいろもんだい、）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。 == 種類 == ; 2頂点対最短経路問題 : 特定の2つのノード間の最短経路問題。一般的に単一始点最短経路問題のアルゴリズムを使用する。 ; 単一始点最短経路問題（SSSP） : 特定の1つのノードから他の全ノードとの間の最短経路問題。この問題を解くアルゴリズムとしては、ダイクストラ法やベルマン-フォード法がよく知られている。 ; 全点対最短経路問題 : グラフ内のあらゆる2ノードの組み合わせについての最短経路問題。この問題を解くアルゴリズムとしては、ワーシャル-フロイド法が知られている。 このような分類がされているのは、後者の問題が単に前者の問題を初期条件（ノード）を変えて繰り返し解くのではなく、アルゴリズムの過程で得た情報を利用して計算量を減らすことが可能となるからでもある。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「最短経路問題」の詳細全文を読む スポンサード リンク
|