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

dijkstra method

Introduction

Today, I will write about the dijkstra method. This method is algorithm which find the shortest distance. The map is expressed by graph. If you never see this page, look at its page. This page explain the heap structure and definition of graph. The dijkstra method used heap structure, Because heap structure reduce the amout of calculation of dijkstra method.
I use this slide to explain dijkstra.

Overview

  • Algorithm
  • Implementation

Algorithm

This algorithm is 
  1. Decide start node, and this node named A.
  2. Allocate $d=\infty$ for each node, but d=0 for start node.
  3. Adjacent node of A named adj_list.
  4.  For adj in adj_list:  If d of adj > d of A + weight to adj -> d = A + weight to adj.
  5. Remove A from graph network.
  6. Find node which have the smallest d and it named A, and if network have node, back to 4.

I explain this algorithm by drawing.

 I explain algorithm by using this graph.
 Fistly, Decede start node and allocate $d=\infty$ for each node.

 Begin from node A. If d of B is smaller than d of A + weight(2), update d of B. Next, If d of C is smaller than d of A + weight(2), update d of C.

 Next remove A from graph network.
 Next, Begin from B. I do the same thing .


The dijkstra algorithm repeat this operation graph network do not have node.


Implementation

This algorithm take $O(log(|V|^2))$. Because this algorithm take time to search the node which have d of shortest distance.
However the calculation time is reduced to O((E+V)log(V)) by heap structure. Select node which have d of shortest distance by picking up node from heap structure.


I will implement the dijkstra by Python 3.
This implementation is published this github page.

I make random 100 node and , number selected by random from 0~30 edge.



Result...



This gif is expressed to update d of each node.












Labels:

コメント

コメントを投稿

このブログの人気の投稿

Theorem of K-means

Introduction 日本語 ver Today, I will write about the theorem of K-means algorithm. K-means algorithm is a method to do clustering about K of class. The post of implement K-means is Implement kernel K-means This post is written about kernel K-means. The kernel K-means is the method which covers the weak point of K-means. I will explain kernel K-means another post. Overview 1 of K coding scheme prototype vector Distortion measure Computing 1 of K coding scheme K-means algorithm is clustering K of class. Now, K-means algorithm expresses that $x_n$ be belong to k like as follows. Let vector $r_n:1 \times K$ is $$r_n := (0,0,..,1,..,0)$$ this vector have 1 in element of k'th and have 0 in else. This expression is called 1 of K coding scheme. Prototype vector K-means algorithm chooses vector which called a prototype. this vector has represented by the cluster. K-means algorithm is regard mean vector as representative of the cluster. I...
コメントを投稿
続きを読む

Thorem of SVM part 2

Introduction 日本語 ver This post is written about theorem of SVM. This post is part 2. Part 1 is written about deriving the objective function. I will write about dual problem. The objective function which deriving in Part 1 is called the main problem. Typically, We optimize not the main problem, but the dual problem. I will write about deriving the dual problem from the main problem. If you until look up part 1, please look up Theorem of SVM part 1 . I implement SVM. It post is Implement linear SVM Implement kernel SVM Overview Main problem Dual problem  Lagurange function maximize L about dual variable, minimize L about primal variable minimize L about primal variable, maximize L about dual variable. Main problem I will review the main problem in Part 1. $$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$$ $$~~s.t~~ \forall i \in N, y_i (w^T \phi(x_i) + b) \geq 1 - \epsilon_i ,~~~, \forall i \in N~\epsilon \geq 0$$ This problem is called s...
コメントを投稿
続きを読む

K-means 理論編

Introduction English ver 今日はK-meansアルゴリズムの理論について書きます。 K-meansアルゴリズムはクラスタリングのためのアルゴリズムです。 K-meansの実装の記事は カーネルK-meansの実装 を御覧ください。 この記事はカーネルK-menasの実装についての記事ですが、通常のK-meansの実装も行っています。カーネルK-meansについてはまた、今度別の記事で紹介したいと思います。 概要 1 of K 符号化法 プロトタイプ 歪み尺度 最適化 1 of K 符号化法 K-meansはK個のクラスについて分類することを考えます。 K-meansでは $x_n$がkのクラスに属していることを次のように表します。 ベクトル$r_n:1 \times K$ を $$r_n := (0,0,..,1,..,0)$$ このベクトルはk番目にのみ1を持ち、それ以外は0を要素に持つようなベクトルです。 こののような表現の仕方を1 of K符号化法と呼びます。 プロトタイプ K-meansではプロトタイプと呼ばれるベクトルを選びます。このベクトルは各クラスに一つあり、そのクラスの代表のようなベクトルです。 K-means ではそのようなベクトルは各クラスの平均ベクトルとなります。これは目的関数から自然と導かれます。 歪み尺度 プロトタイプベクトルを $\mu_i ~\forall k \in K$とします。 この時、k-meansの目的関数は次のようになります。 $$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$$ ここで、 $r_{nk}$ は$r_n$のk番目の要素です。 この目的関数について少し説明をします。$r_{n}$は$x_n$が属しているクラスのラベルの場所だけ1で他は０であるので、 $$J = \sum_{n=1}^{N} ||x_n - \mu_{x_n}||$$ ここで、$\mu_{k_n}$は$x_n$が属しているクラスのプロトタイプです。 よって、 $$J = ||x_1 - \mu_{x_1}|| + ||x_2 -\mu_{x_2}|| + ...
コメントを投稿
続きを読む