我有一个初始有向图 G，我不时从中删除边(从不添加新边)。我不删除节点(尽管有些节点可能最终断开连接)。 有没有一种方法可以有效地重新计算最短路径而无需再次从头开始运行 Dijkstra？初始节点永远不会改变。
如果没有 Dijkstra 算法的增量版本，其他一些算法也可以。但是我不能使用 A*(我记得它有一个增量版本)，因为我没有任何启发式方法可以知道我离目的地有多远。
谢谢
最佳答案
您可以跟踪使用的边。如果删除一个，则可以使用它们找到所有需要更新的节点。
其余节点不需要更新。如果删除边缘，则只能使路径变长。
遍历所有边缘，如果源不需要更新但目标确实将目标添加到 Dijkstra 优先级队列。 完成后运行常规 Dijkstra 算法来计算新成本。
也就是说，如果您从源中删除其中一个链接，您可能仍会运行整个 dijkstra。所以这可能只有在您不尝试删除使用过的链接时才有用(因为很有可能删除的链接无论如何都不会被使用)或者如果您删除链接使其远离源(这样您只需要更新几个节点)。
关于algorithm - 增量 Dijkstra 或最短路径算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33115847/