キンサクプログラマー

お金儲けと技術のメモ

毎日アルゴリズム(第3日目)ダイクストラ法 その1

毎日どころか毎週もやっていないアルゴリズムだけど、この名前で続けようと思う。
3日目は最短経路問題でよく出るダイクストラ法。
いろんなサイトで解説されているが、下記のサイトが個人的には理解しやすかったので、
参考にされたし。 ちなみにソースは次回 その2で。
qiita.com

ダイクストラ法とは

エドガー・ダイクストラが考案した最短経路探索アルゴリズム動的計画法に近い(というか一種?)の手法。
各ノードの結合が非負である場合に適用可能な手法で、負の値がある場合はベルマンフォード法を使う。

アルゴリズム

  1. 最小コスト決定済みノードor最小コスト未決定のうち、コスト最小のノードを選択
  2. 選択されたノードから繋がるノードへのコストを計算し、小さい場合はコストを更新
  3. 1,2を繰り返す
ポイント

最小コストノードから順番に計算することで、無駄な計算を削減している。単純に考えると、あるノードに着目した場合、最小コストが決定するのは、ノードに結合する全ての経路計算をする必要がありそうだが、最小コストノードから探していくと、後から出てくるのは前の値を上回るようにできている。 賢い。

余談:エドガー・ダイクストラ

ダイクストラ法の考案者であるエドガー・ダイクストラは構造化プログラミングや自己安定化アルゴリズムの提唱者。チューリング賞も受賞されている。goto文除去運動なんかもやっていたらしい。

余談の余談:自己安定化アルゴリズム(self stabilization)

分散システムにおいて、どんな初期状態から開始した場合でも、目的とする解を得ることができるようなアルゴリズム
故障に対する対策として提唱された概念である。