shortestPathTo sometimes returns incorrect answer due to incorrect node visit order about scala-graph HOT 6 CLOSED

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

from scala-graph.

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

from scala-graph.

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

from scala-graph.

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

from scala-graph.

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

from scala-graph.

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

from scala-graph.