ダイクストラ法とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > デジタル大辞泉 > ダイクストラ法の意味・解説 

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

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

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


ダイクストラ法

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/04/23 10:17 UTC 版)

最短経路問題 > ダイクストラ法
ダイクストラ法の動作のアニメーション

ダイクストラ法(だいくすとらほう、: Dijkstra's algorithm)はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。

概要

ダイクストラ法は、1959年エドガー・ダイクストラによって考案された。 応用範囲は広くOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されている。

ほかのアルゴリズムとして、

  • 最短経路長の推定値を事前に知っているときは、ダイクストラ法の改良版であるA*アルゴリズムを用いて、より効率的に最短経路を求めることができる。
  • 辺の重みが全て同一の非負数の場合は幅優先探索がより速く、線形時間で最短路を計算可能である。
  • 無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズム[1]によって線形時間での計算が可能であるが、実用性はあまり高くない[要出典]
  • 辺の重みに負数を含む場合はベルマン-フォード法がある。

擬似コード

ダイクストラ法の擬似コードは以下の通りである[2]。始点(スタート)から全てのグラフの頂点への最短経路を求める。

  • Optimization computes maxima and minima.
非線形(制約付き)
凸最適化
組合せ最適化
メタヒューリスティクス


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「ダイクストラ法」の関連用語

ダイクストラ法のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



ダイクストラ法のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
デジタル大辞泉デジタル大辞泉
(C)Shogakukan Inc.
株式会社 小学館
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのダイクストラ法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS