Shortest Path Algorithm With Updates

3
votes

There are N cities and there are M bidirectional roads connected to them , I have to find the shortest path between two fixed cities A and B.

But the problem is there are Q queries given such that path between two cities is blocked , i have to find the shortest path in each Q queries.

My time Complexity in my brute force Algorithm is O(QNlogN) which give me Time Limit Exceeded Error, How can i improve my solution please Help

Pseduo Code:

for u in Q:
  cin>>a>>b;
graph[a][b] = graph[b][a] = INFINITY VALUE
dijkstra algorithm();
cout<<Distance[D]<<endl;

Problem LINK

MY CODE Which Is giving me Time Limit Exceeded Error

Plese Help How can I improve my algorithm ?

1
javaalgorithmshortest-path
There are plenty of posts here on this site that cover the Shortest Path or Djikstra's algorithm you should look them up, or go google. – David Coler
possible duplicate of the best shortest path algorithm – David Coler
@DavidColer his time complexity shows that he is using Dijkstra's algorithm – Pham Trung
@DavidColer please read the question carefully , it's is not about shortes path it's about how to Djikstra algorithm effect if one path is blocked – user4406103
@PhamTrung yes but my question is little different please read it carefully – user4406103

1 Answers

3
votes

The paper Vickrey Prices and Shortest Paths: What is an edge worth? by John Hershberger and Subhash Suri shows how to solve this problem in time O(NlogN+M) where N is the number of vertices, and M is the number of edges.

This allows you to precalculate the M answers depending on which road is blocked, so you can answer each query in O(1), for a total complexity of O(NlogN+M+Q).