@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 <gon...@gmail.com> 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 <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.
