更新的最短路径算法

Question

有N个城市，它们之间有M条双向道路相连。我需要找到两个指定城市A和B之间的最短路径。但问题是有Q个查询，其中路径被阻塞了，我需要在每个查询中找到最短路径。我的暴力算法时间复杂度为O(QNlogN)，这导致了超时错误。请问如何改进我的解决方案？请帮忙。

伪代码如下：

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

问题链接

我的代码，但是出现了超时错误

请帮忙改进我的算法。

- user4406103

---

这个网站上有很多关于最短路径或Djikstra算法的帖子，你应该查找它们，或者去谷歌搜索。 - David Coler

可能是最佳最短路径算法的重复问题。 - David Coler

@DavidColer 的时间复杂度表明他正在使用 Dijkstra 算法。 - Pham Trung

@DavidColer 请仔细阅读问题，这不是关于最短路径的问题，而是关于如果一条路径被阻塞了Djikstra算法会如何影响的问题。 - user4406103

@PhamTrung，是的，但我的问题有点不同，请仔细阅读。 - user4406103

Answer 1

该论文“Vickrey Prices and Shortest Paths: What is an edge worth?”展示了如何在时间复杂度为O(NlogN+M)的情况下解决这个问题，其中N是顶点数，M是边数。

这使得您可以预先计算出M个答案，具体取决于哪条道路被阻塞，因此您可以在O(1)的时间内回答每个查询，总复杂度为O(NlogN+M+Q)。

- Peter de Rivaz