如何在有向加权图中将一条边精确设置为零以找到最短路径？

Question

以下是我正在研究的问题：

考虑一个有向加权图 G ，其中所有边的权重都是正的。这个问题的目标是找到G 中 两个预先指定的顶点s 和 t之间 的最短路径 ，但有一个额外的扭曲：您可以将（您选择的）恰好一条边的权重更改为零。

换句话说，您必须在G 中选择一条边 以设置为零，以最小化s 和 t之间的最短路径 。给出一个有效的算法来在O ( E lg V )时间内实现这个目标， 并分析你的算法的运行时间。次优解决方案将获得较少的信用。

提示：您可能需要反转边缘，多次运行熟悉的算法，并做一些额外的工作

所以我尝试将 Dijkstra 从s运行到所有其他节点，然后我尝试反转边缘并再次从s运行它到所有其他节点。但是，我发现我们必须从s到所有其他节点运行 Dijskstra ，然后反转边，然后从所有其他节点运行 Dijkstra到t。我不确定这如何帮助我们找到设置为零的边缘。根据我的直觉，我认为我们只需将最大权重边缘设置为零。反转边缘有什么意义？

Answer 1

我们需要运行 Dijkstra 算法两次 - 一次用于原始图s作为源顶点，一次用于反转图并t作为源顶点。我们将表示顶点s和i第一次运行D(i)之间的距离以及顶点t和i第二次运行之间的距离D_rev(i)。

请注意，我们可以向后跟随反向边（即沿原始方向跟随它们），因此D_rev(i)实际上是从顶点i到的最短距离t。同样，D(i)是从顶点s到i遵循 Dijkstra 算法的最短距离。

现在，我们可以遍历所有的边缘，并为每个边e它连接v1和v2，加起来D(v1)和D_rev(v2)，对应于路径的权重s -> v1 -> v2 -> t与e被零边缘，因为我们可以从去s到v1与的距离D(v1)，设置e为0，从v1到v2，然后从v2到t的距离D_rev(v2)。这些中的最小值就是答案。

一个粗略的证明草图（也是一个重述）：如果我们将一条边设置e为 0，但不在路径中使用它，我们最好将路径中的一条边设置为 0。因此，我们只需要考虑包含归零边的路径。通过零边的最短路径e是首先从s到的最短路径v1，然后从v2到的最短路径t，这正是使用 Dijkstra 算法计算的，即D和D_rev。

希望这个回答有帮助！