|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ダイクストラ ： [だいくすとら] (n) Dijkstra, (n) Dijkstra ・ 法 ： [ほう] 1. (n,n-suf) Act (law: the X Act)
ダイクストラ法（だいくすとらほう、）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。辺の重みに負数を含む場合はベルマン-フォード法などが使える。辺の重みが全て同一の非負数の場合は幅優先探索が速く、線形時間で最短路を計算可能である。また、無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズムによって線形時間での計算が可能であるが、実用性はあまり高くない。 == 概要 == ダイクストラ法はグラフ上の2頂点間の最短経路を求めるアルゴリズムで、1959年エドガー・ダイクストラによって考案された。 応用範囲は広くOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されている。 なお最短経路の推定値を事前に知っているときは、ダイクストラ法の改良版であるA *アルゴリズムを用いて、より効率的に最短経路を求めることができる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ダイクストラ法」の詳細全文を読む スポンサード リンク
|