Introduction
今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this pageを見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。
このスライドはダイクストラ法を説明したスライドです。
Overview
このグラフを使って説明します。
初めに、スタート地点を決めます。そして、各ノードに$d=\infty$を割り当てます。
Aから始まります。Aの隣接ノードであるBのdを更新します。もし、現在のBよりもAのdとA->Bへの重みを足したもののほうが小さいならdをその値に更新します。同じようにCnのdを更新します。
次にAを取り除きます。
次はBから始まります。Aと同じことをやります。
今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this pageを見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。
このスライドはダイクストラ法を説明したスライドです。
Overview
- アルゴリズム
- 実装
アルゴリズム
このアルゴリズムは
- スタート始点のノードを決める。そして、それをAと名付ける。
- 各ノードに$d=\infty$を割り当てる。ただし、スタート地点はd=0
- Aの隣接ノードのリストをadj_listと名付ける。
- For adj in adj_list: If d of adj > d of A + weight to adj -> d = A + weight to adj.
- グラフnetworkからAを取り除く
- グラフnetworkの中で最初のdを持っているノードをAとし、4に戻る。
となっています。
このアルゴリズムを図を用いて説明します。
このアルゴリズムを図を用いて説明します。
このダイクストラ法では今のような操作をグラフの全てのノードに×がつくまで続きます。
実装
このアルゴリズムでは$O(log(|V|^2))$という計算量を持っています。最小のdを持つノードを探すのに時間がかかります。
しかし、ヒープ構造を使えばO((E+V)log(V))に減らせます。ヒープ構造で現時点でのノードのdをヒープ構造で保存しておけば、ヒープ構造から取り出せば、最小のdを持つノードを簡単に取り出せます。
ダイクストラ法はPython 3で実装しました。
コードはgithubに乗せています。
100個のノードを作り、各ノードに0~30の間からランダムな数を選択しedgeを作ります。
結果は
このgifは各ノードの最短距離の更新を表したものです。
コメント
コメントを投稿