だいくすとらほう

デジタル大辞泉

ダイクストラ‐ほう〔‐ハフ〕【ダイクストラ法】

読み方：だいくすとらほう

《Dijkstra's algorithm》最短経路問題を効率的に解くアルゴリズムの一。ノードとエッジで構成されたグラフで、ある2点間の距離を最短にする経路の候補を、各ノードに距離またはコストなどの値を付与し、その和が最小になるよう順次更新して経路の選択をする。鉄道路線の経路検索などに用いられる。1959年、オランダの計算機科学者E＝ダイクストラが考案。

OR事典

ダイクストラ法

読み方：だいくすとらほう
【英】：Dijkstra's algorithm

1959年, ダイクストラによって提案された最短路問題を解くための基本的なアルゴリズムの 1つ. すべての枝が非負のときに適用可能. まず, 各点毎に始点からの距離の自明な上限を距離ラベルとして用意し, 適切な順に距離ラベルの修正を繰り返すことにより, 各点までの(最短)距離を順に確定していく. すべての点の距離ラベルが確定したときに終了する. 結果的に始点から全点への最短路の情報が同時に求まる.

「OR事典」の他の用語

グラフ･ネットワーク：

クラスター分析  グラフ  シュタイナー最小木  ダイクストラ法  ダルメジ・メンデルゾーン分解  デルタマトロイド  ナップサック問題