增量式Dijkstra或最短路径算法？

Question

我有一个初步的有向图 G，我会偶尔删除其中的边缘（但不会添加新的）。尽管某些节点可能最终变得不连通，但我不会删除节点。

有没有一种有效的方法可以重新计算最短路径，而无需从头开始运行 Dijkstra 算法？起始节点永远不会改变。

如果没有增量版本的 Dijkstra 算法，那么其他算法也可以。但我不能使用 A*（我记得它有一个增量版本），因为我没有任何启发式来知道离目的地还有多远。

谢谢

- excalibur1491

Answer 1

你可以跟踪使用的边缘。如果删除其中一个，则可以使用它们找到所有需要更新的节点。

其余的节点不需要更新。如果删除边缘，只能使路径更长。

遍历所有边缘，如果源不需要更新但目标需要，请将目标添加到Dijkstra优先级队列中。 完成后，运行常规的Dijkstra算法以计算新成本。

话虽如此，如果从源中删除其中一个链接，仍然可能运行整个dijkstra。因此，如果您不尝试删除已使用的链接（例如，有很大的可能性链接未被使用），或者如果您删除了与源远离的链接（这样您只需要更新少量节点），那么可能只有在这种情况下才有用。

- Sorin

---

我想我知道你的意思，但如果我一次删除两个边怎么办（这可能发生）？这意味着我需要按照特定的顺序将这些边的头节点放入堆栈中，不是吗？首先是距离源更远的那一个，然后是更近的那一个？谢谢。 - excalibur1491