JOIN
 Revision History
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search My Post History  |  My Watches  |  User Settings Forums Tutorial Discussions Introduction to graphs and their data structures dijskra: is there something missing in the article? Revision History (1 edit)
 dijskra: is there something missing in the article? Here is how I interpret the dijktra algorithm in the article (see below): Add the start node neighbors, then pick a high priority node from those, add its neighbours to the same heap,result: you have mixed the contents of the previous node with current one so that if the heap is remade it is possible the high priority node(top) wont be the one below the current node. Can someone clarify this, that my line of thinking. The code from the article is given below. void dijkstra(node start) { priorityQueue s; s.add(start); while (s.empty() == false) { top = s.top(); s.pop(); mark top as visited;check for termination condition (have we reached the target node?)add all of top's unvisited neighbors to the stack. }}
 dijskra: is there something missing in the article? Here is how I interpret the code below: Add first neighbors to start node, then pick a high priority node, add its neighbours to the same heap,result: you have mixed the contents of the previous node with current one so that if the heap is remade it is possible the high priority node(top) wont be the one below the current node. Can someone clarify this, that my line of thinking. The code from the article is given below. void dijkstra(node start) { priorityQueue s; s.add(start); while (s.empty() == false) { top = s.top(); s.pop(); mark top as visited;check for termination condition (have we reached the target node?)add all of top's unvisited neighbors to the stack. }}