• 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 #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
 
 
0 #193 bulgaria 2019-08-20 01:47
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 #192 paris 2019-08-08 18:25
Nice replies in return of this query with real arguments and describing the whole thing on the topic
of that.
Quote
 
 
0 #191 paris 2019-08-08 18:24
Nice replies in return of this query with real arguments and describing the whole thing on the topic
of that.
Quote
 
 
0 #190 parkolas 2019-08-01 14:16
With havin so much written content do you ever run into any problems of plagorism or copyright violation? My blog has a lot of unique
content I've either created myself or outsourced but it
looks like a lot of it is popping it up all over the internet without
my agreement. Do you know any ways to help protect
against content from being stolen? I'd definitely appreciate it.
Quote
 
 
0 #189 france 2019-07-29 19:00
I am really enjoying the theme/design of your website. Do you ever
run into any internet browser compatibility problems?
A number of my blog visitors have complained about my site not working correctly
in Explorer but looks great in Safari. Do you have any suggestions to help fix
this issue?
Quote
 
 
0 #188 france 2019-07-29 18:58
I am really enjoying the theme/design of your website. Do you ever
run into any internet browser compatibility problems?
A number of my blog visitors have complained about my site not working correctly
in Explorer but looks great in Safari. Do you have any suggestions to help fix
this issue?
Quote
 
 
0 #187 france 2019-07-29 18:57
I am really enjoying the theme/design of your website. Do you ever
run into any internet browser compatibility problems?
A number of my blog visitors have complained about my site not working correctly
in Explorer but looks great in Safari. Do you have any suggestions to help fix
this issue?
Quote
 
 
0 #186 цигари ева видове 2019-07-27 17:29
Therefore, people ingest more day time online.
Quote
 
 
0 #185 self-Stockage 2019-07-23 09:59
L'entreposage de vos affaires ont des intérêts certains : cela offre la
possibilité de veiller ses meubles de manière sécurisée dans un garde-meubles
adapté et nette. Tout le matériel : chariots, transpalettes,...

est à votre disposition
Quote
 
 
0 #184 евтини цигари 2019-07-07 04:40
Therefore, people need more time online.
Quote
 
 
0 #183 Référencement Seo 2019-07-06 19:10
Consultant Référencement Google et vrai autodidacte, Nicolas Sotton à
appris à construire des sites e-commerce, les héberger sur le net et les positionner en 1er page des moteurs comme Google.
Nicolas à fait de la publicité web sa spécialité !
Quote
 

Add comment

No bad words.


Security code
Refresh


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