给定一个带边权的无向图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的最短路径的成本
去掉边缘
返回产生最短路径的候选边
但是还有更好的吗？
最佳答案
一种方法是：
从a运行dijkstra并在a[n]中存储到每个节点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之间的最短路径。
关于algorithm - 找到一条使A到B的最短路径减少最多的边，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26225385/