[algogeeks] Re: wiki issue on dijkstra's algorithm
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_algorithmwiki/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 1721. however, by following dijkstra's, you would get 1491 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.
[algogeeks] Re: wiki issue on dijkstra's algorithm
@krunal that's just different representation On Oct 11, 9:26 am, Krunal Modi krunalam...@gmail.com wrote: Each edge will have a cost not the nodes(vertices). Upload an image of the graph. -- 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.
[algogeeks] Re: wiki issue on dijkstra's algorithm
@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_algorithmwiki/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 1721. however, by following dijkstra's, you would get 1491 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.
[algogeeks] Re: wiki issue on dijkstra's algorithm
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 david.c...@gmail.com 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 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_algorithmwiki/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 1721. however, by following dijkstra's, you would get 1491 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.
[algogeeks] Re: wiki issue on dijkstra's algorithm
Each edge will have a cost not the nodes(vertices). Upload an image of the graph. -- 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.
[algogeeks] Re: wiki issue on dijkstra's algorithm
I have a dijkstra-algoritm-program in php here. If you can send me an adjacent matrix like this: 1 2 3 4 5 2 0 x x x 3 x 0 x x 4 x x 0 x 5 x x x 0 Or better a 2-dimensional array with (start, end, cost) $map = array ( 1, 2, 10, 2, 4, 10, 3, 4, 10, 4, 5, 5, 5, 7, 8, ) of your above problem I can re-check the output from my dijkstra- program (no guarantee) for you. On Oct 7, 3:23 pm, ligerdave david.c...@gmail.com wrote: anyone here? On Oct 6, 10:47 am, ligerdave david.c...@gmail.com wrote: so i was reading a href=http://en.wikipedia.org/wiki/ Dijkstra's_algorithmwiki/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 1721. however, by following dijkstra's, you would get 1491 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.
[algogeeks] Re: wiki issue on dijkstra's algorithm
anyone here? On Oct 6, 10:47 am, ligerdave david.c...@gmail.com wrote: so i was reading a href=http://en.wikipedia.org/wiki/ Dijkstra's_algorithmwiki/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 1721. however, by following dijkstra's, you would get 1491 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.
