频繁重复 Dijkstra 算法的潜在优化？

Question

我正在解决一个编程问题，涉及找到顶点和图的其余部分之间的最短路径。目前，我正在使用 Dijkstra 算法来实现这一点。

但是，问题涉及多次调用 Dijkstra's，每次只需稍作修改（更改边的权重），然后写入输出。

我担心用简单的算法本身来做到这一点。图表可能会变得非常大，因此需要进行的修改数量也会很大。

我不知道我能做什么。我想过 Python 的

cache

装饰器，但我使用的是 C++（只允许使用 C++ 或 Pascal），我不确定

cache

是否对此有帮助。

这是一份纸质作业。没有在线判断或大样本输入，并且关于顶点、边、修改的最大数量以及内存和时间限制的约束并不真正明确。不过，内存限制很可能是1GB，时间限制是1s。

Answer 1

首次运行 Dijkstra 时，您将存储每个顶点距源的距离。

如果您随后从 u->v 修改边的权重，则只需在新权重小于

dist(v)-dist(u)

时更新距离。

如果您需要更新距离，那么您可以再次运行Dijkstra，或者您可以使用从v开始的修改版本，该版本仅考虑距离减少的顶点。