• Increase font size
  • Default font size
  • Decrease font size

Dijkstra's algorithm

Dijkstra's algorithm named after Dutch computer scientist Edsger Dijkstra who discovered it in 1956 and published in 1959.

 

What is it?

- it is a graph search algorithm. It means when you want to use it, you have to have a graph (map) of the world. Edges of the graph can not have negative cost.

 

What it does?

- finds a shortest path from a single source to a single destination. Since the alg. useses costs, the shortest path means the path with the lowest cost.

 

Note:

- graph consists of nodes (vertexes) and edges. In this alg. there has to be assigned a cost for every edge.

 

Example of use:

- we are located at the position A and want to move to position Z. If there other positions {B,C,D,....} between our start and end possition with a differenct distances, we can use Dijkstra's algorithm to find the shortest path from A to Z. Distances between every position would be the costs of the edges of the graph and positions would be vertexes (nodes).

 

Practial usage:

- Dijkstra's algorithm is in real life used by CISCO routers when using link-state routing protocols - OSPF, IS-IS. Physical position of the router represents a vertex and paths between specific networks represent edges. To each path is given a cost - how good or bad the connetion is, and the value of cost is propagated between routers. Each router informs other routes about the costs he knows.

 

Useful link:

This page contains excelent materials about not only Dijkstra's algorithm.

Pseudocode:

 
function Dijkstra(Graph, source):
// Initializations
for each vertex v in Graph:
 
// Distance = cost from source node to v-th node
dist[v] := infinity ;                                // One can use a huge number e.g. "1000000" as approximation for infinity.
 
// Previous node in optimal path from source
previous[v] := undefined ;                           // One cau use e.g. "-1" => -1st node does not exist, so we say is not defined.
end for
 
dist[source] := 0 ;                                  // Distance from source to source is 0, so cost = 0
Q := the set of all nodes in Graph ;                 // All nodes in the graph are unoptimized - thus are in Q
 
while Q is not empty:                                // Loop until we find the path
u := vertex in Q with smallest distance in dist[] ;  // Which is actually the start node in first case. At the beginning all nodes have cost of "1000000" and the start node has cost of "0".
 
remove u from Q ;                                    // Somehow mark the node as alredy examined
 
if dist[u] = infinity:                               // Test if it is worth it to examine u-th node.
break ;                                              // All remaining vertices are inaccessible from source
end if
 
for each neighbor v of u:                            // Where v-th node has not yet been removed from Q.
 
alt := dist[u] + dist_between(u, v) ;                // alt - possible alternative best distance
if alt < dist[v]:                                    // alt is better than dist[v] so overwrite dist[v]
dist[v] := alt ;
previous[v] := u ;                                   // Remember a path to this node, because the point is important, it has a good cost.
end if
end for
end while
return dist;

 

How to get the shortest path?

S := empty sequence                                           // Stack "S" will contain our path 
 u := target
 while previous[u] is defined:                                 // Construct the shortest path by looking backwards - traverse from end to start
 insert u at the beginning of S                            // Push the vertex into the stack "S"
 u := previous[u]                                          // Traverse from target to source
 end while ;

Demo

The demo below demonstrates how Dijkstra's algorithm works. There are 2 white rectangles. The left one is the start position and the right one is the position we want to get. Obviously there is also an obstacle between them so the algorithm has to find the way around it.

 

 

Comments  

 
0 #56 Katja 2017-11-12 16:21
yߋu're realⅼy a excellent webmaster. The
websiote loading velocity iѕ incredible. It sort of feels that yoս are doing any unique
trick. Also, The contents аrе masterwork.
уou have doine a еxсeklent task on this matter!

my site; nspmost effective weight loss diet - Katja: http://jogosdeculinaria.com/__media__/js/netsoltrademark.php?d=meelink.hol.es%2Fweight_loss_fast_139305&popup=1 -
Quote
 
 
0 #55 FirstWayne 2017-11-04 18:06
I have noticed you don't monetize your site, don't waste your traffic, you
can earn additional cash every month because you've got high quality content.

If you want to know how to make extra bucks, search for: Boorfe's tips best adsense alternative
Quote
 
 
0 #54 dịch thuật giá rẻ 2017-10-04 09:18
My brother suggested I might like this blog. He was entirely right.

This post actually made my day. You cann\'t imagine just how much time I had spent for this info!
Thanks!
Quote
 
 
0 #53 Vegatel.Su 2017-10-03 05:53
Hi there! This articloe could not be written any better!
Looking at this post reminds me of my previous roommate! He always kept talking
about this. I am going to forward this post to him.

Fairly certain he'll have a very good read. I appreciate you for
sharing!

Feel free to surf to my homepage :: Аренда квартир в Аликанте (Vegatel.Su: http://vegatel.su/?option=com_k2&view=itemlist&task=user&id=27601:pattimoris16294887)
Quote
 
 
0 #52 paintball 2017-09-27 20:54
Very nice post. I just stumbled upon your blog and wanted to say that I've really loved surfing around your weblog posts.
In any case I'll be subscribing in your rss feed and I am hoping you write once more soon!
Quote
 
 
0 #51 diamond jewelry 2017-09-26 02:41
Beѕides thosе two methοds, there are lots of other options to scrub and gaze afteг youг pearl
and ɗiamond jewelry: http://stores.ebay.com/DIAMOND-SCENE
еarrings. There is also another specifications about the quality
of cut which is the 'finish' and also thе 'symmetry' with the Ԁiamond.
A pⅼɑstic deformation can be the main cause of Ьrown, pink and reԁ coⅼors in diamonds.
Quote
 
 
0 #50 mata kuliah Ekonomi 2017-08-21 05:22
For newest information you have to pay a visit web and
on world-wide-web I found this web page as a most excellent site
for latest updates.
http://ejournal.gunadarma.ac.id/index.php/dekons/article/view/1136 mata kuliah ekonomi manajemen s1: http://www.gunadarma.ac.id/id/page/yulisdin-mukhlis-st-mt.html

Stop by my blog: mata kuliah Ekonomi: http://nelly_sofi.staff.gunadarma.ac.id/Downloads/files/20434/PENGUMUMAN+BEASISWA+PPA+dan+BBM+2010.pdf
Quote
 
 
0 #49 alamat Ban pt 2017-08-16 09:55
Wow! After all I got a webpage from where I be capable of genuinely takle valuable data regarding my study and knowledge.

http://spma.gunadarma.ac.id/wp-content/uploads/2010/06/3.-Prosedur-Publikasi-Universitas.pdf mata kuliah
ilmu hukum: http://library.gunadarma.ac.id/journal/view/14043/implementasi-algoritma-kunang-kunang-untuk-penjadwalan-mata-kuliah-di-universitas-ma-chung.html/

my blog :: alamat Ban pt: http://sap.gunadarma.ac.id/upload/KK-042238.pdf
Quote
 
 
0 #48 Mata Kuliah It 2017-08-12 11:19
Your method of telling the whole thing inn this paragraph is
genuinely fastidious, all bee able to simply be aware of Mata Kuliah It: http://www.gunadarma.ac.id/en/page/thesis-defence-of-doctoral-in-information-technology-tavipia-rumambi-and-robby-chandra.html, Thanks
a lot.
http://sap.gunadarma.ac.id/upload/AK-051211.pdf mata kuliah
manajemen pemasaran: http://ugpedia.gunadarma.ac.id/content/12/772/id/beasiswa-prestasi-akademik.html
Quote
 
 
0 #47 teknik mesin unp 2017-08-09 15:54
Very nice post. I just stumbled upon yoir weblog and wanted to say that I've really enjoyed browsing
yolur blog posts. In any case I'll be subscribing to your rss
feed and I hope you write again soon!
http://ftp.gunadarma.ac.id/linux/docs/v06/Kuliah/SistemOperasi/BUKU/SistemOperasi-4.X-1/ch21s05.html beasiswa s1
di jepang 2016: http://ftp.gunadarma.ac.id/android/sdk/sdk_310712/docs/guide/developing/devices/emulator.html

Feel free to surf to my web page ... teknik mesin unp: http://ftp.gunadarma.ac.id/linux/docs/v06/Kuliah/Seminar-MIS/2006/175/175-10-From_The_Vendors_Perspective.pdf
Quote
 

Add comment

No bad words.


Security code
Refresh


Design by i-cons.ch / etosha-namibia.ch