Fix implementation of Dijkstra's algorithm #1745
Conversation
Relying on `bestWeights` doesn't work if the node was added several times with exactly the same weight.
| @@ -208,8 +209,9 @@ object Graph { | |||
| while (toExplore.nonEmpty && !targetFound) { | |||
| // node with the smallest distance from the target | |||
| val current = toExplore.dequeue() // O(log(n)) | |||
| if (current.key != sourceNode) { | |||
| val currentWeight = bestWeights(current.key) // NB: there is always an entry for the current in the 'bestWeights' map | |||
There was a problem hiding this comment.
Are you sure about that change?
At first glance getting the best weight from this map seems useful, doesn't it?
There was a problem hiding this comment.
It's exactly the same weight. We already have it in current.weight, there is no point in getting it from somewhere else.
Actually we could remove bestWeights completely, it's not needed by the algorithm, the comparison between the different weights for a node is done inside the priority queue.
Now it's just used to know when to update bestEdges and it sometimes prevents adding useless weights to the priority queue.
There was a problem hiding this comment.
the comparison between the different weights for a node is done inside the priority queue.
Right, I glossed over that point, once you realize this it's obviously not needed.
Ensure that we only visit each node once in Dijkstra's algorithm.