Priority Queue

[sfwhite]

Have you considered switching out from your own priority queue implementation to a Fibonacci Heap implementation? FH has one of the best amortized runtimes for Dijkstra implementations.

The mnemonist library has an implementation that's stable.