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$
3
  • 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, 2012 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, 2012 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, 2012 at 23:32

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .