删除边后对最短路径的影响

Question

已经提供了有向图的输入，并且我已经使用异步和同步Bellman-Ford算法找到了到特定节点'T‘的最短路径。我试着找出一些边被删除后对最短路径的影响。在我的方法中，我试图将删除边的起始节点处的距离标记为无穷大，并试图应用异步Bellman-Ford，但我在该点处卡住了，因为其他节点不会更新它们的值，因为它们已经具有最短路径的最小值。

有没有人可以帮我找出一种新的最短路径，而不必在新的图上再次运行完整的算法？

Answer 1

你不能。在贝尔曼-福特算法本身中可以找到一个简单的解释：

如果V是节点集。从起始节点到任何其他节点的最小路径将通过最大|V|个节点( |V|-1条边)。这就是为什么您将边松弛|V|-1次，以便来自所有节点的“信息”将传播到源。

如果您已经在图上应用了Bellman-Ford算法，则可以开始松弛所有已删除节点的邻居，并将更改传播到它们的邻居，直到没有使用已删除节点的路径(直到没有进行任何更新)。意识到负循环。