well the animation could have marked the last node with red, they probably got lazy and skipped the last step.
Both the algorithm part, and the pseudocode does seem ok to me. However, both of them are too cluttered. I have to say that the pseudocode in CLRS introduction to algorithms MIT press is excellent, both concise and easy to understand. On Oct 12, 4:37 pm, ligerdave <[email protected]> wrote: > @Ercan exactly. so do you also find the wiki somewhat misleading? > especially the animation? looks to me when it finds the min, it stops > and reset the start node to be the min and start over again. > > or, > > if you have more vertices between nodes in my example above, you are > able to find the shortest path by following wiki steps. > > On Oct 12, 2:05 am, Gönenç Ercan <[email protected]> wrote: > > > > > Dijkstra's algorithm is a dynamic programming algorithm. no matter > > which path is first discovered, the relax operation (if the new path > > is shorter update the path to the node, step 3) will find the correct > > answer in the end. The smallest distance criteria, which selects the > > next current node (step 5) ensures that an already visited node can > > not be relaxed (no shorter path to there). One big mistake is, > > terminating the algorithm when the destination node is reached. The > > first path discovered is not necessarily the correct solution. Your > > problem in particular is that, you are choosing the smallest distance > > node only from the path you are discovering. So lets trace this > > algorithm. > > > Assume that vertices are letters from bottom to up, left to right; A, > > B, C, D, E, F > > > A -> B,C (discovered costs 7, 4) A is marked as visited > > C -> E (discovered cost is 13) C is marked as visited > > Remember that we choose the smallest distance to initial node. one of > > the nodes B or E (costs: 7 or 13) > > B -> D (discovered, cost 9) B is marked as visited > > D-> F (discovered, cost 10) D is marked as visited > > -------- We should nt stop here, we still have unvisited node E. In > > this example E does not relax the path to F, but it should be checked > > in general or the solution may not be minimal. > > E -> F (already discovered, its current cost is 10, since 14 is not > > smaller, no relax operation) > > > All nodes are visited, we are done. Output the path A -> B -> D -> F > > > On Oct 6, 5:47 pm, ligerdave <[email protected]> wrote: > > > > so i was reading <a href="http://en.wikipedia.org/wiki/ > > > Dijkstra's_algorithm">wiki</a> on dijkstra's algorithm for finding > > > shortest path. i dont think article specifically define the > > > requirements of the graph in order to make the algorithm working > > > properly.(unless i missed something?) > > > > for instance, in the graph below, the shortest path from 1to1 should > > > be 1>7>2>1. however, by following dijkstra's, you would get 1>4>9>1 > > > because compared to 7, 4 is smallest among all direct vertices. > > > > 1 > > > / \ > > > 2 9 > > > | | > > > 7 4 > > > \ / > > > 1 > > > > anyone knows the requirements, especially the ration of #of edges to > > > #of vertices? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
