增量Dijkstra或最短路径算法？

Question

我有一个初始有向图G，从中我不时删除边（不添加新的边）。我不删除节点（尽管有些可能会断开连接）。 有没有办法有效地重新计算最短路径而无需再次从头开始运行Dijkstra？初始节点永远不会改变。

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

谢谢

Answer 1

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

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

贯穿所有边缘，并且如果源不需要更新，但目标确实将目标添加到Dijkstra优先级队列。 一旦你完成了运行常规Dijkstra算法来计算新的成本。

这就是说你可能仍然运行整个dijkstra，如果你从源头中删除一个链接。因此，如果您不尝试删除已使用的链接（因为很可能无法删除已删除的链接），或者删除链接以使其距离源代码很远（这样您只需要更新几个节点）。