增量 Dijkstra 或最短路径算法?

Incremental Dijkstra or shortest path algorithm?

我有一个初始有向图 G,我不时从中删除边(从不添加新边)。我不删除节点(尽管有些节点可能最终断开连接)。 有没有一种方法可以在没有 运行 Dijkstra 的情况下再次从头开始有效地重新计算最短路径?初始节点永远不会改变。

如果没有Dijkstra算法的增量版本,其他算法也可以。但是我不能使用 A*(我记得它有一个增量版本),因为我没有任何启发式方法可以知道我离目的地有多远。

谢谢

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

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

运行 通过所有边缘,如果源不需要更新但目标确实将目标添加到 Dijkstra 优先级队列。 完成后 运行 使用常规 Dijkstra 算法计算新成本。

也就是说,如果您从源中删除其中一个 link,您可能仍然 运行 整个 dijkstra。所以这可能只有在您不尝试删除使用过的 link 时才有用(因为很有可能删除的 link 无论如何都不会被使用)或者如果您删除 link这样它就远离源(这样你只需要更新几个节点)。