Custom priority queues for Dijkstra & Co

[gdalle]

At the moment, shortest path algorithms such as Dijkstra and A* rely on the standard PriorityQueue from DataStructures.jl, partly because it supports updating the priority value of a stored element.

However, there are alternative implementations that do not require this property, and those can be faster in many cases.
Would it make sense to add a method that lets the user choose the priority queue they want, along with the version of the algorithm (with or without priority updates)?

[gdalle]

Here is an example of benchmark that shows the promise of this idea
https://gdalle.github.io/FastPriorityQueues.jl/dev/benchmarks/
ping @etiennedeg if you want to add some more tests when you have time

[simonschoelly]

Is there really a good use case for letting the user choose their own priority queue? Maybe we should just pick the fasted one for them.

Also, currently the priority queue used for a_star is parametrized with Integer, an abstract data type - we might already be able to improve performance by using a concrete type there:

Graphs.jl/src/shortestpaths/astar.jl

Line 78 in 9039378

open_set = PriorityQueue{Integer, T}()

[gdalle]

It doesn't cost much to define dijkstra!(queue, ...) internally and then add a default choice

[gdalle]

See https://discourse.julialang.org/t/fast-er-priority-queues/81269 for a discussion and some benchmarks

[etiennedeg]

Seems we can get about a 2x acceleration based on the HeapPriorityQueue. For unweighted graphs, it would also be nice to specialize the code. Because the priority queue at any given point will only hold two different values, I think we can avoid priority queue by storing vertices in two queues: one with the vertices at the currently evaluated distance, and one with vertices one unit further.

[gdalle]

For unweighted graphs, isn't Dijkstra just BFS?

[gdalle]

For which, by the way, an iterator would be nice (see #106)