以下是我正在研究的问题：
考虑一个 所有边权重均为正的有向加权图G。这个问题的目标是在 G中找到 两个预先指定的顶点 s 和 t之间的最短路径 ，但有一个额外的转折：您可以将（您选择的）恰好一条边的权重更改为零。
换句话说，您必须在 G 中选择一条边设置为零，以最小化 s 和 t之间的最短路径 。给出一个在O ( E lg V )时间内实现这一目标的有效算法， 并分析你的算法的运行时间。次优解决方案将获得较少的信用。
提示：您可能需要反转边缘，多次运行熟悉的算法，并做一些额外的工作
因此，我尝试将 Dijkstra 从s运行到所有其他节点，然后尝试反转边缘并再次从s运行到所有其他节点。但是，我发现我们必须将 Dijskstra 从s运行到所有其他节点，然后反转边缘，然后将 Dijkstra 从所有其他节点运行到t。我不确定这如何帮助我们找到设置为零的边缘。根据我的直觉，我认为我们只需将最大权重边缘设置为零。反转边缘有什么意义？
我们需要运行 Dijkstra 算法两次 - 一次用于s作为源顶点的原始图，一次用于反向图并t作为源顶点。我们将顶点s与i第一次运行之间的距离表示D(i)为顶点t与i第二次运行之间的距离D_rev(i)。
请注意，我们可以向后跟随反转的边缘（即，沿原始方向跟随它们），因此D_rev(i)实际上是从顶点i到的最短距离t。类似地，是从顶点到遵循 Dijkstra 算法D(i)的最短距离。si
我们现在可以遍历所有边，并且对于连接 和 的每条边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。
希望这个答案有帮助！