以下是我正在研究的问题:
Consider a directed, weighted graph G where all edge weights are positive. The goal of this problem is to find the shortest path in G between two pre-specified vertices s and t , but with an added twist: you are allowed to change the weight of exactly one edge (of your choosing) to zero.
In other words, you must pick an edge in G to set to zero that minimizes the shortest path between s and t . Give an efficient algorithm to achieve this goal in O ( E lg V ) time and analyze your algorithm’s running time. Sub-optimal solutions will receive less credit.
Hint: You may have to reverse the edges, run a familiar algorithm a number of times, plus do some extra work
所以我尝试将 Dijkstra 从 s 运行到所有其他节点，然后我尝试反转边缘并再次从 s 运行它到所有其他节点。但是，我发现我们必须从 s 到 所有其他节点 运行 Dijskstra，然后反转边缘，然后从 所有其他节点 运行 Dijkstra > 到 t。我不确定这如何帮助我们找到设置为零的边缘。根据我的直觉，我认为我们可以简单地将最大权重边缘设置为零。反转边缘有什么意义？
最佳答案
我们需要运行 Dijkstra 算法两次 - 一次以 s 作为源顶点的原始图，一次以 t 作为源顶点的反转图。我们将从第一次运行中得到的顶点 s 和 i 之间的距离表示为 D(i) 并且我们得到的顶点之间的距离t 和 i 第二次运行 D_rev(i)。
请注意，我们可以向后跟随反转的边(即沿原始方向跟随它们)，因此 D_rev(i) 实际上是距 顶点的最短距离i 到 t。类似地，D(i) 是按照 Dijkstra 算法从顶点 s 到 i 的最短距离。
我们现在可以遍历所有边，对于连接 v1 和 v2 的每条边 e，加起来 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。
希望这个回答对您有所帮助!
关于algorithm - 如何在有向加权图中将一条边恰好设置为零以找到最短路径？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47836714/