2
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – dtldarek Nov 28 '12 at 22:49
  • 1
    $\begingroup$ 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! $\endgroup$ – TonyK Nov 28 '12 at 23:08
  • $\begingroup$ I tried to give some intuition along an answer to a previously asked question: math.stackexchange.com/questions/45683/… $\endgroup$ – user3533 Nov 28 '12 at 23:32
5
$\begingroup$
 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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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