• 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 #207 eridanuspills.com 2020-02-02 20:59
Wow i like yur site. It really helped me with the information i wus looking for. Appcriciate it, will bookmark.
Quote
 
 
0 #206 Voyance Audiotel 2020-01-27 08:49
Mélody est une spécialiste de la voyance par correspondance surtout dans le secteur de l'amour.

Elle vous permettra d'obtenir les solutions sur votre futur sentimental.
prennez contact avec elle directement au 06.60.59.09.24.
Quote
 
 
0 #205 eridanuspills.com 2020-01-20 03:05
I have joined your feed and look forward to seeking more of your great post.
Quote
 
 
0 #204 best way 2020-01-17 04:30
Great amazing things here. I am very satisfied to look your article. Thank you so much and i’m looking ahead to touch you. Will you kindly drop me a mail?
Quote
 
 
0 #203 voyance discount 2020-01-12 20:17
vous pensez qu'une clairvoyance au tel n'est pas de la même qualité qu'en cabinet
? www.styl-voyance.com est un centre de divination qui vous donnera une solution rapide et discrète n'hésitez plus.
Quote
 
 
0 #202 mama bear t shirt 2019-11-29 13:39
Excellent post. I am going through many of these issues as well..
Quote
 
 
0 #201 vêtements sports 2019-11-27 20:32
l'identité de la marque est le pilier de votre identité, il est ainsi important de prendre en charge que sa diffusion soit inédite et unique vis-a-vis de l'adversité.

les professionnels de rueduprint.fr peuvent vous conseiller.
Quote
 
 
0 #200 https://sr.wanjk.de/ 2019-11-22 20:31
Therefore, people set aside more evening online.
Quote
 
 
0 #199 informatique 2019-10-26 16:37
L'un de vos clients se plaint d'un souci de performance sur votre site web ?
Make-it-simple donne accès à un logiciel qui donne la possibilité de résoudre ce genre de problème grâce à l'analyse dynamique.
Venez poser vos demandes dans le site.
Quote
 
 
0 #198 SEO 2019-10-19 14:13
Vous recherchez un conseiller search engine optimization ou
un développeur web ? Contactez mr sotton, également connu sous le nom de nicolaseo, c'est un expert en marketing sur le net.
voilà son site web : https://www.nicolas-sotton.ch/
Quote
 
 
0 #197 Services seo 2019-10-08 06:09
consultant chez search engine optimization W
LLC ( société spécialiste de le référencement ), nicolas sotton a
dirigé l'implantation de ce projet seo dans le secteur de france.
c'est un passionné par son travail et crée d'autres projets spécialisés sur celui-ci.
Quote
 
 
0 #196 drapeau publicitaire 2019-08-26 06:02
Vous chercher un très bon support d’appel publicitaire
tendance et dynamique ? Ne désirez plus, la communauté de Drapeau Print pourra fabriquer
pour vous un drapeau à votre image avec un vaste
choix d'échantillons mais aussi de catégories.
venez visiter leur site web
Quote
 
 
0 #195 bulgaria 2019-08-20 01:48
Hi, I do think this is an excellent site. I stumbledupon it ;) I am going to revisit yet again since I book marked it.
Money and freedom is the best way to change, may you be rich and continue to guide other people.
Quote
 
 
0 #194 bulgaria 2019-08-20 01:48
Hi, I do think this is an excellent site. I stumbledupon it ;) I am going to revisit yet again since I book marked it.
Money and freedom is the best way to change, may you be rich and continue to guide other people.
Quote
 

Add comment

No bad words.


Security code
Refresh


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