スキップしてメイン コンテンツに移動

ダイクストラ法

Introduction

今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this pageを見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。
このスライドはダイクストラ法を説明したスライドです。

Overview

  • アルゴリズム
  • 実装

アルゴリズム

このアルゴリズムは
  1. スタート始点のノードを決める。そして、それをAと名付ける。
  2. 各ノードに$d=\infty$を割り当てる。ただし、スタート地点はd=0
  3. Aの隣接ノードのリストをadj_listと名付ける。
  4.  For adj in adj_list:  If d of adj > d of A + weight to adj -> d = A + weight to adj.
  5. グラフnetworkからAを取り除く
  6. グラフnetworkの中で最初のdを持っているノードをAとし、4に戻る。
となっています。
このアルゴリズムを図を用いて説明します。

 このグラフを使って説明します。
 初めに、スタート地点を決めます。そして、各ノードに$d=\infty$を割り当てます。

 Aから始まります。Aの隣接ノードであるBのdを更新します。もし、現在のBよりもAのdとA->Bへの重みを足したもののほうが小さいならdをその値に更新します。同じようにCnのdを更新します。

次にAを取り除きます。
 次はBから始まります。Aと同じことをやります。


このダイクストラ法では今のような操作をグラフの全てのノードに×がつくまで続きます。


実装

このアルゴリズムでは$O(log(|V|^2))$という計算量を持っています。最小のdを持つノードを探すのに時間がかかります。
しかし、ヒープ構造を使えばO((E+V)log(V))に減らせます。ヒープ構造で現時点でのノードのdをヒープ構造で保存しておけば、ヒープ構造から取り出せば、最小のdを持つノードを簡単に取り出せます。


ダイクストラ法はPython 3で実装しました。
コードはgithubに乗せています。

100個のノードを作り、各ノードに0~30の間からランダムな数を選択しedgeを作ります。



結果は



このgifは各ノードの最短距離の更新を表したものです。



Labels:

コメント

コメントを投稿

このブログの人気の投稿

離散フーリエ変換

Introduction English ver 今日は離散フーリエ変換について書きます。 現在、シグナル解析についてのpdfを作成中です。このpdfは github で公開中です。 シグナル解析は、courseraのレクチャーで勉強中です。 ここ にリンクを貼っておきます。 pdfは随時更新中です。
2 件のコメント
続きを読む

heap structure

Introduction 日本語 ver Today, I will write about heap structure. The heap structure is one of the data structure. My reason of studying heap structure is that I joined seminar of Ritsumeikan Univ. I used this  slide  in seminar of Ritsumeikan Univ. Overview data structure binary tree heap Implementation heap sort Data structure I will explain about data structure before explaining about heap. Data structure is how to keep data. Data structure is selected on the basis of operation which you want to.  Heap belong to data structure called priority queue. priority queue have purpose which  add data pick up minimum data (and remove)  Binary Tree Let, E and V are sets. The element $e \in E$ is called edge. The element $v \in V$ is called node. g:E->V×V is map to V × V from E. (E,V,g) is called graph. For example, The arrows are edge. The circles are node. This is expressed map. It is possible to go to node 3 from 1....
コメントを投稿
続きを読む

LIMIT and user variable in MysQL

Problem 日本語 ver I want to use this query in PROCEDURE. SET @user_variable = FLOOR(RAND()*10); INSERT INTO  Table_name (columns_name) VALUES (1) FROM Table_name ORDER BY RAND() LIMIT 1 OFFSET @user_variable; This query want to substitute 1 for the @user_variable 'th line of columns_name, but this query does not work. A cause is that LIMIT and OFFSET does not user variable. Solution SET @user_variable = FLOOR(RAND()*10); PREPARE SET_STMT FROM 'INSERT INTO  Table_name (columns_name) VALUES (1) FROM Table_name ORDER BY RAND() LIMIT 1 OFFSET ?;';  EXECUTE SET_STMT USING @user_variable; Conclusion, if you want to use user variable with LIMIT or OFFSET, use PREPARE STATMENT. Reference http://techtipshoge.blogspot.com/2011/10/limit.html
2 件のコメント
続きを読む