Multiple shortest path queries on a big graph

Revision en1, by m.boniecki, 2021-02-19 17:47:00

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?

Tags graphs, shortest paths

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English m.boniecki 2021-02-25 01:26:51 168 Add one more possible speedup (published)
en1 English m.boniecki 2021-02-19 17:47:00 766 Initial revision (saved to drafts)