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

Question

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

谁能帮我找出一种方法来找到新的最短路径，而不必在新图上再次运行完整的算法？

Answer 1

你不能。并且可以在 Bellman-Ford 算法本身中找到一个简单的解释：

如果 V 是节点集。从起始节点到任何其他节点的最小路径将通过最大值 |V| 节点（|V|-1 边）。这就是为什么要放松边缘 |V|-1 时间，以便来自所有节点的“信息”传播到源。

您是否已经在图上应用了 Bellman-Ford 算法，您可以开始放松所有已删除节点的邻居并将更改传播到他们的邻居，直到没有使用已删除节点的路径（直到没有进行更新）。意识到负循环。