Even with 6500 vertices, you have a total max of 6500^2 edges (after filtering for minimum distance per edge, which is very fast). Using a performant language s

Even with 6500 vertices, you have a total max of 6500^2 edges (after filtering for minimum distance per edge, which is very fast). Using a performant language such as C++ and a priority queue there is no way that you would reach even 10s for a single djikstras.