shortestPathTo sometimes returns incorrect answer due to incorrect node visit order

[fiadliel]

shortestPathTo implements Dijkstra's algorithm for selecting the shortest path between two nodes. It appears that the implementation is incorrect, and the wrong answer is sometimes given.

From http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Select the unvisited node that is marked with the smallest tentative distance, and set it as the new "current node" then go back to step 3.

However, the priority queue used to select the next node uses the node's distance from one of its predecessors, not the current smallest tentative distance from the start. This may mean that new nodes (which should already have a large distance) may be visited before earlier nodes, and the algorithm may terminate incorrectly.

[fiadliel]

This is an example graph which gives the wrong answer:
https://github.com/garycoady/scala-graph/commit/dc3f3ed0b2b63c41615aad2ecbd92af5f93bc508

[fiadliel]

On larger graphs, just adding nodes to the priority queue with the correct weight causes a crippling slowdown for me (but at least it's giving the right answer). Probably because the same node may be added to the priority queue potentially many times. What is really wanted is a way of updating the ordering of the queue as the tentative distance of a node changes, like what is described in http://algorithms.soc.srcf.net/notes/dijkstra_with_heaps.pdf

[peter-empen]

Hi Gary, thanks for reporting and even providing a test and the accompanying fix! Would you mind creating a pull request later on?

[fiadliel]

No problem! I've opened a pull request (now that I understand the problem, there's a better test case included).

[peter-empen]

It seems we can close this issue due to your fix documented in #10. Any objectives?

[fiadliel]

I think it's fixed, thanks for reviewing/accepting the changes!