Recently my friend told me about the following problem. We are given connected undirected weighted graph with n ≤ 100000 vertices and m ≤ 400000 edges. Now we have to answer q ≤ 2500 queries. In each query you have to find shortest path between given pair of vertices.
I am curious how to solve this problem efficiently. Obviously we can run Dijkstra algorithm q times, but on a such a big graph I suppose this will be too slow. The only speedups I came up with are:
- Meet in the middle technique. For each query we can run Dijkstra algorithm from source and target vertex and stop after finding the first path.
- After running Dijkstra search for answer to the other queries in tree of the shortest paths.
I believe that in pessimistic case they will be as slow as naive solution.
Do you know any faster solution?
Auto comment: topic has been updated by m.boniecki (previous revision, new revision, compare).
_ We are given connected undirected weighted graph_
If your graph is acyclic, sure, we can do better.
OMG LTDT is back!
It's not acyclic.
In the general case there's no solution. However, I do remember an extremely similar problem where it was given that the answer for all queries would be greater than some large number (think $$$N/10$$$). That's probably where your friend got it from. I can't find the original problem, but it was in some OI contest.
It may have been a XXVI polish OI https://szkopul.edu.pl/problemset/problem/QHh99tBu4p9FMsFohv4da7S7/site/?key=statement