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 this will be definitely too slow. The only speed up I know is 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. Still in pessimistic case it will be as slow as naive solution.

Do you know any faster solution?