Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can someone succinctly explain how Dijkstra's algorithm works and how it may be used to find the shortest path for such a graph (from a to z)?

graph

I've looked at some procedures online, but many of them seem to differ and it's hard to discern what I'm actually trying to accomplish.

Thanks for the help!

share|improve this question
2  
The net is swarming with explanations of Dijkstra algorithm and I don't think we need yet another one here. On the other side, should you have any concrete questions, I will be glad to help. –  dtldarek Nov 28 '12 at 22:49
1  
If I were Edsger Dijkstra, I would be annoyed that my name was associated with such a transparent and obvious algorithm. As if I hadn't done anything better! –  TonyK Nov 28 '12 at 23:08
    
I tried to give some intuition along an answer to a previously asked question: math.stackexchange.com/questions/45683/… –  user3533 Nov 28 '12 at 23:32
add comment

1 Answer

up vote 4 down vote accepted
 You will start from a and you will put a label 0. After that you will find all the unsolved nodes, like b (label 2) and c(label 3) . You will chose the node with the smallest label. So we will continue with b( label 2) 

For now we have route a(0)-b(2);

  • We continue to expand the unsolved nodes, so we will have: d((label b) + 5 = 7) ,e((label b) + 2 = 4) and c (label = 3). We will chose c because it has the smallest label.
    • We continue to expand the unsolved nodes, so we will have: d((label b) + 5 = 7) ,e((label b) + 2 = 4). We will chose e because it has the smallest label ."4"
      • We continue to expand the unsolved nodes, so we will have: d((label e) + 1 = 5) ,z((label e) + 4 = 8). We will chose d because it has the smallest label ."5"
      • We continue to expand the unsolved nodes, so we will have: z((label e) + 4 = 8). We will chose z because it has the smallest label ."8"

Maybe this tutorial will help you: http://optlab-server.sce.carleton.ca/POAnimations2007/DijkstrasAlgo.html

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.