JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums Tutorial Discussions Introduction to graphs and their data structures Re: dijskra: is there something missing in the article? Revision History (3 edits)
Re: dijskra: is there something missing in the article? (response to post by mafoko)
I've always thought Dijkstra does the following:

set all L[i] to infinity
set L[start] to zero.
add all vertices to the priority queue.
while the queue is not empty {
top = the item from queue with lowest L[]
remove top from queue
mark top as visited
update all L[]'s for neighbours of top (if L[i]+D[i,j]<L[j] then ...) and update the queue accordingly
}

What's written in the article seems to be strange in the sense that it adds the vertex to the queue for each incoming edge, thus requring more space. Athough it seems to be still working correctly and have the same E*log(V) working time. Instead of keeping track of current minimal distance to the vertex, it keeps minimal distances through each of the incoming edges, but since only the first value (the minimal one) is used, it doesn't do any harm to the correctness.

The reason for that strangeness may be that STL's priority_queue doesn't provide means to update the queue when some priorities change, although it's easy when implementing the heap by yourself.
Re: dijskra: is there something missing in the article? (response to post by mafoko)
I've always thought Dijkstra does the following:

set all L[i] to infinity
set L[start] to zero.
add all vertices to the priority queue.
while the queue is not empty {
top = the item from queue with lowest L[]
remove top from queue
mark top as visited
update all L[]'s for neighbours of top (if L[i]+D[i,j]<L[j] then ...) and update the queue accordingly
}

What's written in the article seems to be strange in the sense that it adds the vertex to the queue for each incoming edge, thus requring more space. Athough it seems to be still working correctly and have the same E*log(V) working time. Instead of keeping track of current minimal distance to the vertex, it keeps minimal distances through each of the incoming edges, but since only the first value (the minimal one) is used, it doesn't do any harm to the correctness.

The reason for that strangeness may be that STL's priority_queue doesn't provide means to update the queue when some priorities change, although it's easy when implementing the heap by yourself.>
Re: dijskra: is there something missing in the article? (response to post by mafoko)
I've always thought Dijkstra does the following:

set all L[i] to infinity
set L[start] to zero.
add all vertices to the priority queue.
while the queue is not empty {
top = the item from queue with lowest L[]
remove top from queue
mark top as visited
update all L[]'s for neighbours of top (if L[i]+D[i,j]<L[j] then ...) and update the queue accordingly
}

What's written in the article seems to be strange in the sense that it adds the vertex to the queue for each incoming edge, thus requring more space. Athough it seems to be still working correctly and have the same E*log(V) working time. Instead of keeping track of current minimal distance to the vertex, it keeps minimal distances through each of the incoming edges, but since only the first value (the minimal one) is used, it doesn't do any harm to the correctness.

The reason for that strangeness may be that STL's priority_queue doesn't provide means to update the queue when some priorities change.>
Re: dijskra: is there something missing in the article? (response to post by mafoko)
I've always thought Dijkstra does the following:

set all L[i] to infinity
set L[start] to zero.
add all vertices to the priority queue.
while the queue is not empty {
top = the item from queue with lowest L[]
remove top from queue
mark top as visited
update all L[]'s for neighbours of top (if L[i]+D[i,j]<L[j] then ...) and update the queue accordingly
}>