一个特定的州在其 V 个城市中有一组 E 条道路，其中从城市 u 到邻近城市 v 穿过这条道路的时间由 cuv 给出。 (注意 cuv 不一定等于 cvu——实际上可能没有从 v 到 u 的路。)暴风雪过后，有些道路无法通行，但州长需要尽快从城市 s 开车到城市 t，这么快有时间只清理一条无法通行的道路。给出一个复杂度为 O(E log V ) 的算法，该算法确定要犁哪条路(只有一条)，以实现从城市 s 到城市 t 的可能时间最少的路径。输入是所有道路的列表、每条道路的值 cuv、s、t 以及不可通行的道路集。如果道路清理没有帮助，算法应该这样说。
我认为解决这个问题最接近的方法是使用 Dijkstra 的算法来寻找最短路径，但是，由于我们不知道哪条路不能通行，哪条路可以通行，因此 Dijkstra 的算法似乎不适合这个问题。那么，是否有任何其他算法能够检查每条边的情况并找到最短路径？抱歉我的逻辑，我不太理解这个问题，任何回复或提示都会有所帮助，谢谢。
谁能解释一下我的问题与 Shortest path between two vertices when exactly one edge weight can be reduced by 50%? 有何相似之处？
最佳答案
我们将给定的图称为 G(V, E)，其中 E 可以拆分为 D + F，其中 D 代表可通行的道路，F 代表不可通行的道路。
按照评论中的建议，复制图形，因此您有 G(V,D) 和 G'(V',D')。对于任何给定的顶点 u ∈ V，都有一个“复制”顶点 u' ∈ V'。所以还有一个 s' 和一个 t'。我们此时不包括 F 或 F'。
然后定义一组边F°为(u,v')，对于每条边(u,v) ∈ F .因此，F° 中的这些边是从 V 到 V' 的可通过连接——仅在那个方向上。
让我们称这个新图为 G°(V°, E°)，其中 V° = V + V'，E° = D + D' + F° 和 F° 如上一段所定义。
现在解决在 G° 中从 s 到 {t, t'} 的问题。由于从 V' 到 V 没有边，以 t' 结尾的解路径将只使用一条边 (u, v') 来自 F°。请注意，如果通过比 t' 更短的路径到达 t，这意味着不使用 F° 的边(不需要不可通行的道路被犁)。
在 G° 中寻找 s 和 {t, t'} 之间的最短路径的问题现在是一个标准问题，可以用 Dijkstra 算法求解。还需要做一件事:对于每个访问过的 w' ∈ V'，F° 的边 (u,v') —— 即被越过到达那里 - 需要记录。该信息应该传递给算法访问的下一个顶点，以便当最终找到 t' 时，可以立即给出答案，即边 (u,v' )。
该算法中访问的边数最多为|E°| = |D + D' + F°| ≤ 2|E| = O(|E|)。该算法只访问每条边一次，所以时间复杂度为O(|E|)。
关于algorithm - 寻找最短路径的 Dijkstra 算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58261758/