dijkstra method

Introduction

日本語 ver

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.

Reference
[1] https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E3%83%81%E3%83%A3%E3%83%AC%E3%83%B3%E3%82%B8%E3%83%96%E3%83%83%E3%82%AF-%E7%A7%8B%E8%91%89-%E6%8B%93%E5%93%89/dp/4839931992