Content deleted Content added
→Algorithm: reply |
|||
Line 96:
:It's not wrong: when node 4's distance changes that is the 'tentative distance' mentioned in step 3 changing. At that point node 4 is not the current node, node 3 is. 4 is being checked as a neighbor of the current node at 3.
:The all nodes termination is fine, too. Dijkstra's algorithm finds the minimal distance between a particular node and all other nodes in the graph (not a single destination), so it's obviously never going to terminate when run against an infinite graph. You need some variant of Dijkstra (such as [[A*_search_algorithm|A*]] to handle infinite graphs. - [[User:MrOllie|MrOllie]] ([[User talk:MrOllie|talk]]) 14:58, 9 August 2011 (UTC)
For me, the confusing steps are 2 and 3. On step 2, you mark all nodes as ''unvisited'' and next, on step 3, you add all neighbors of current node to the ''unvisited set''. Firstly, is there a reason for the unvisited-mark when having a visited-mark? Secondly, maybe the ''unvisited set'' is also unnecessary (as it just binds useful space), because the nodes belonging to this set are those who have distance less than infinity and are not marked as visited. [[User:Vevek|Vevek]] ([[User talk:Vevek|talk]]) 23:28, 15 August 2011 (UTC)
| |||