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!

  • 0
    I tried to give some intuition along an answer to a previously asked question: http://math.stackexchange.com/questions/45683/dijkstras-algorithm-proof/45702#457022012-11-28

1 Answers 1

5
 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