> 16000 teleportation edges [...] doesn't include physical travel edges between the vertices
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.
I agree. Maybe it was hand implemented in python with lots of memory allocation and a few defects that made it accidentally quadratic.
or some IO/parsing got mixed into the processing of each node. big-o is one problem. Forgetting or not noticing the constants is another