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 bedefinitely too slow. The only speed ups I know is mcame up with are:↵
↵
1. 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↵
2. After running Dijkstra search for answer to the other queries in tree of the shortest paths.↵
↵
I believe that in pessimistic caseitthey will be as slow as naive solution.↵
↵
Do you know any faster solution?
↵
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
↵
1. 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.
2. After running Dijkstra search for answer to the other queries in tree of the shortest paths.↵
↵
I believe that in pessimistic case
↵
Do you know any faster solution?
