• 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 #66 BestMadonna 2018-11-19 08:25
I have noticed you don't monetize your page, don't waste your traffic, you
can earn additional cash every month. You can use the best adsense alternative for any type of
website (they approve all websites), for more details simply search in gooogle:
boorfe's tips monetize your website
Quote
 
 
0 #65 BestMilan 2018-10-27 06:53
I have noticed you don't monetize your site, don't waste your traffic, you
can earn extra bucks every month. You can use the best adsense alternative for any type of website (they approve all websites),
for more info simply search in gooogle: boorfe's tips monetize your website
Quote
 
 
0 #64 LesleeJuicy 2018-10-20 11:09
Hi. I see that you don't update your site too often. I know that
writing articles is boring and time consuming. But did you know
that there is a tool that allows you to create new articles using existing content (from article directories or other blogs from your niche)?
And it does it very well. The new posts are high quality and pass
the copyscape test. Search in google and try: miftolo's
tools
Quote
 
 
0 #63 DominikJuicy 2018-08-23 03:05
Hi. I see that you don't update your website too often. I know that writing articles is boring and time consuming.
But did you know that there is a tool that allows you to create
new posts using existing content (from article directories or other websites from your niche)?
And it does it very well. The new posts are unique and
pass the copyscape test. Search in google and try: miftolo's tools
Quote
 
 
0 #62 Lela 2018-07-09 09:59
Heya i am ffor thhe firѕt time here. I came across tһis Ьoard and I find It truly useful & it
helped me oout a lot. I hope tߋ give something back and aid
others like you hslped me.

Here is my blog :: pocket knife keychain - Lela: https://www.justpaste.it/schweizerknive -
Quote
 
 
0 #61 hébergement internet 2018-05-03 23:10
Héberger un site web gratuitement avec la liste des hébergements
gratuit proposé par des webmasters Francophone : https://www.ghstools.fr/forum/viewforum.php?f=40 Vous pouvez proposer d'autres hébergement gratuit et laisser
votre avis sur votre hébergeur.
Quote
 
 
0 #60 Richardescaw 2018-04-03 13:24
This is nicely said! !
dose size of cialis Cialis generico safe dosage for cialis Buy cialis from australia: http://cialisyoues.com/#
import cialis Buy cheap cialis in canada generic low dose cialis Cialis daily: http://cialisyoues.com/#
buying cialis in colombia http://cialisyoues.com/# only here cialis pills http://cialisyoues.com/#: http://cialisyoues.com/#
Quote
 
 
0 #59 agama carissa putri 2018-03-19 02:14
http://tinyurl.com/yblwxj75 lirik lagu rio febrian memang harus
pisah
http://tinyurl.com/y7dt55y3 konser rio febrian
foto artis esa sigit: http://tinyurl.com/jll2toj
http://tinyurl.com/y72l9bxd biodata grace natalie
http://tinyurl.com/ybeqtn2m esa sigit amanda
amel carla dan lintang: http://tinyurl.com/y8xyk4wu
Quote
 
 
0 #58 carabine junior 2018-02-03 17:00
Achat Pistolet a plomb pas cher sur Matraque-Telescopique.com votre boutique armurerie en ligne
spécialiste dans la vente de Pistolet CO2, pistolet à plomb, revolver à plomb, carabine à air et à plomb...
Quote
 
 
0 #57 tonfa police 2018-01-29 04:53
Tonfas, matraque et bâton de Police en vente sur https://www.matraque-telescopique.com Spécialiste dans la vente d'armes de défense sur Internet.
Acheter des armes utilisé par la Police en vente libre livré chez vous en 48 heures.
Quote
 

Add comment

No bad words.


Security code
Refresh


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