已经提供了有向图的输入，并且我已经使用 - 异步和同步Bellman-Ford算法找到了到特定节点'T'的最短路径 . 我试图在删除一些边缘后找出最短路径上的效果 . 在我的方法中，我试图将删除边缘的起始节点处的距离标记为无穷大，并且尝试应用异步Bellman-Ford，但我陷入困境，因为其他节点不会更新它们的值，因为它们已经是最短的路径最小值 .
任何人都可以帮我找到一种方法来找到新的最短路径而无需在新图上再次运行完整算法？
你不能 . 在Bellman-Ford算法本身中可以找到一个简单的解释：
如果V是节点集 . 从起始节点到任何其他节点的最小路径将通过最大| V |节点（| V | -1边） . 这就是为什么你放松边缘| V | -1时间的原因，所以来自所有节点的'信息'将传播到源 .
您是否已在图表上应用Bellman-Ford算法，您可以开始放宽所有已删除节点的邻居并将更改传播到其邻居，直到未使用已删除节点的路径（直到不进行更新） . 意识到负面循环 .
1 回答
你不能 . 在Bellman-Ford算法本身中可以找到一个简单的解释：
如果V是节点集 . 从起始节点到任何其他节点的最小路径将通过最大| V |节点（| V | -1边） . 这就是为什么你放松边缘| V | -1时间的原因，所以来自所有节点的'信息'将传播到源 .
您是否已在图表上应用Bellman-Ford算法，您可以开始放宽所有已删除节点的邻居并将更改传播到其邻居，直到未使用已删除节点的路径（直到不进行更新） . 意识到负面循环 .