JOIN
Get Time
forums  Revision History
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.

}
}