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?
