最短的路径，一个可跳过的边缘

4 回答

• 4

  首先使用Dijkstra为每个顶点 v 找到从 s 到 v 的最短路径的长度 S(v) . 然后使用Dijkstra为每个顶点 v 找到从 v 到 t 的最短路径的长度 T(v) . 然后对于每个边缘 (v, w) 使用上面的规则找到总和 S(v) + T(w) . 最后，选择最小路径 .

  Note ：在这种方法中，我们使边缘 (v,w) 权重无效并找到通过 (v,w) 的最短路径

  回复于 2024-04-29T10:24:53+08:00
• 7

  问题很简单 .

  假设你有一个带有一个可跳过边缘的最短路径，p = v1，...，vi，vi 1，...，vm和（vi，vi 1）是一个跳过的边缘
  显然，路径（v1，...，vi）是v1和vi之间的最短路径
  路径（vi 1，...，vm）是vi 1和vm之间的最短路径
  将d（x，y）定义为节点x和节点y之间的最短路径的长度
  你可以通过dijkstra算法简单地找到所有节点x的d（s，x）和d（x，t），现在我们必须逐个选择跳过的边 . 换句话说，具有一个可跳过边缘的最短路径的长度是

  对于图中的所有边（u，v），min（d（s，u）d（v，t））

  由于Dijkstra算法，时间复杂度为O（E log V）

  回复于 2024-04-29T10:24:53+08:00
• 1

  之前的答案似乎假设Dijkstra给出了从每个顶点到每个顶点的最短距离，但事实并非如此 .

  如果你只执行一次Dijkstra，从s开始，你有从s到每个顶点的最短路径 .

  为了找到从每个顶点到t的最短距离，有必要在反转图的每个边之后从t开始再次执行Dijkstra .

  完整的解决方案是：

  1）从s开始在图G上执行Dijkstra以获得s与任何v之间的最短距离T（v） .

  2）反转所有边以获得反转图G'

  3）从t开始在图G'上执行Dijkstra，以获得t和任何v之间的最短距离R（v） .

  4）要跳过的是边缘e（v1 - > v2），其中T（v1）R（v2）是最小的 .

  5）要遵循的路径是第一个Dijkstra给出的s和v1之间的最短路径以及第二个Dijkstra给出的v2和t之间的最短路径的串联 .

  回复于 2024-04-29T10:24:53+08:00
• 2

  现有的答案是正确的，但对我来说更直观的另一个想法是转换图表并使用分层方法：

  • 创建图形 G 的副本，并将其命名为 G'

  • 对于 G 中的每个边 (u, v) ，创建一个从 u （在 G 中）指向 v' （在 G' 中）的权重为 0 的边 (u, v') .

  • 使用任何标准最短路径算法（如Dijkstra）计算从 s 到 t' 的最短路径 .

  回复于 2024-04-29T10:24:53+08:00