m.boniecki's blog

Multiple shortest path queries on a big graph
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?

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by m.boniecki (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

_ We are given connected undirected weighted graph_

If your graph is acyclic, sure, we can do better.

→ Reply
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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.

→ Reply