Shortest path algorithm with updates
There are N cities and M bidirectional roads are connected to them, I need to find the shortest path between two fixed cities A and B.
But the problem is that Q-queries are set in such a way that the path between the two cities is blocked, I need to find the shortest path in each Q-query.
My time The complexity is at my brute strength Algorithm is O (QNlogN) which give me time limit exceeded, 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;
MY CODE that gives me the time limit is exceeded
Plese Help How to improve the algorithm?
source to share
Article Pricing and Vickrey's Short Cuts: What is an Advantage? John Hershberger and Subash Suri show how to solve this problem in O (NlogN + M) time, where N is the number of vertices and M is the number of edges.
This allows you to pre-compute the M responses depending on which road is blocked, so you can answer each query in O (1), for a total complexity of O (NlogN + M + Q).
source to share