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 <david.c...@gmail.com> 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
