読者です 読者をやめる 読者になる 読者になる

fnwiyaBlog

EmacsとかLispとか可視化とか

ダイクストラ法

ダイクストラ法はスタート地点から各ポイントまでの最短経路を求めるアルゴリズムです。

概略

  • 動的計画法(手近で明らかなことから順次確定していき,その確定した情報をもとにさらに遠くまで確定していく方法)の一種
  • 負のコストがかかる経路は扱えない
  • スタート地点のコストは0
  • 2つ以上離れたポイントへのコストは無限大
  • 各ポイントへのコストを比較し、不要な経路が分かった時点で以降の計算を省略できる

ダイクストラ法(最短経路問題)

ダイクストラ法による最短ルートの求めかた

経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ

pythonでの実装

Pythonでダイクストラアルゴリズムを実装した - フツーって言うなぁ!