

Revision History 

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.


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.>


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.>


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 }>

