如何在有向加权图中将一条边恰好设置为零以找到最短路径？
How to set exactly one edge to zero in directed weighted graph in order to find shortest path?
以下是我正在处理的问题：
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
所以我尝试 运行ning Dijkstra 从 s 到所有其他节点然后我尝试反转边缘并再次 运行ning 它从s 到所有其他节点。但是，我发现我们必须 运行 Dijskstra 从 s 到 所有其他节点 然后反转边缘然后 运行 Dijkstra 从 所有其他节点 到 t。我不确定这如何帮助我们找到设置为零的边缘。根据我的直觉，我认为我们可以简单地将最大权重边缘设置为零。反转边缘有什么意义？
我们需要 运行 Dijkstra 算法两次 - 一次以 s 作为源顶点的原始图，一次以 t 作为源顶点的反转图。我们将从第一个 运行 到顶点 s 和 i 之间的距离表示为 D(i) 以及顶点 t 和 [= 之间的距离13=]秒运行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.
希望这个回答对您有所帮助！
以下是我正在处理的问题：
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
所以我尝试 运行ning Dijkstra 从 s 到所有其他节点然后我尝试反转边缘并再次 运行ning 它从s 到所有其他节点。但是，我发现我们必须 运行 Dijskstra 从 s 到 所有其他节点 然后反转边缘然后 运行 Dijkstra 从 所有其他节点 到 t。我不确定这如何帮助我们找到设置为零的边缘。根据我的直觉，我认为我们可以简单地将最大权重边缘设置为零。反转边缘有什么意义？
我们需要 运行 Dijkstra 算法两次 - 一次以 s 作为源顶点的原始图，一次以 t 作为源顶点的反转图。我们将从第一个 运行 到顶点 s 和 i 之间的距离表示为 D(i) 以及顶点 t 和 [= 之间的距离13=]秒运行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.
希望这个回答对您有所帮助！