algorithm - 找到使从 A 到 B 的最短路径减少最多的边

Question

给定一个具有边权重的无向图 G，一组候选边(长度 |V| + |E|)，以及顶点 A 和 B，找到使从 A 到 B 的最短路径减少最多的边。

例如:

候选边是虚线。从 A 到 B 的最短路径是 A -> C -> D -> G -> B(成本 7)。但是对于边 (D, B)，最短路径是 A -> C -> D -> B(成本 6)，因此算法应该返回 (D, B)。

我想出了一个蛮力解决方案 O((|V| + |E|)^2 log |V|):

• 对于每个候选边:
  • 将边添加到图中
  • 运行 Dijkstra 计算从 A 到 B 的最短路径的成本
  • 去掉边
• 返回导致最短路径的候选边

但是还有更好的吗？

Answer 1

一种方法是:

• 从 A 运行 Dijkstra 并将到每个节点 n 的距离存储在 A[n] 中
• 从 B 运行 Dijkstra 并将到每个节点 n 的距离存储在 B[n] 中
• 遍历每条候选边。对于连接顶点 x 和 y 的权重为 w 的边，比较 w+A[x]+B[y] 和 w+A[y]+B[x]

w+A[x]+B[y] 和 w+A[y]+B[x] 中的较小者给出了使用候选边时 A 和 B 之间的最短路径。