4 ms·
10 minutes for Dijkstra on a graph with only 6500 vertices and 16000 edges sounds fishy - I'd expect that to take way less than a second.
by rav 8y ago
10 minutes for Dijkstra on a graph with only 6500 vertices and 16000 edges sounds fishy - I'd expect that to take way less than a second.
- Deestan 8y ago> 16000 teleportation edges [...] doesn't include physical travel edges between the vertices
- ball_of_lint 8y agoEven 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.
- shoo 8y agoI agree. Maybe it was hand implemented in python with lots of memory allocation and a few defects that made it accidentally quadratic.
- amichal 8y agoor some IO/parsing got mixed into the processing of each node. big-o is one problem. Forgetting or not noticing the constants is another