m.boniecki's blog

By m.boniecki, history, 3 years ago, In English

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:

  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 they will be as slow as naive solution.

Do you know any faster solution?

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it