找到一条边缘,最大限度地减少从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并将距离存储到A [n]中的每个节点n
• 从B运行Dijkstra并将距离存储到B [n]中的每个节点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之间的最短路径.