最短路径算法的变种

Question

我们给出了一个带有两个源和两个目标顶点(比如s1,s2,d1,d2)的加权无向图.从源1到目的地1和源2到目的地2的成本定义为:

• 如果边缘仅使用两条路径中的一条,则使用边缘的成本等于权重.
• 如果边缘被用于两个路径(s1 - > ..-> d1和s2 - > ..-> d2),则使用边缘的成本等于权重的1.5倍.

总之,如果两条路径使用相同的边缘,则总成本增加"1.5 x重量"而不是"2 x重量".鼓励使用共同边缘.

如果路径使用具有相反方向的边缘,则不会降低成本.

有任何帮助,想法或建议来确定最小化总成本的算法吗？

Answer 1

我建议首先使用Floyd Warshall在时间O(n ^ 3)中找到所有对最短路径,其中n是顶点数.

一旦你拥有它,你可以计算沿最短路径走s1-> d1和s2-> d2的成本,这为你提供了成本的上限.

做得更好的唯一方法是使用共享路径.如果是这样,则s1和s2将会聚在顶点A,然后沿共享路径前往顶点B,然后分割为d1和d2.

因此算法是尝试所有顶点A,B对,并使用对之间的预先计算的最短路径d(x,y)计算最小值:

d(s1,A)+d(s2,A)+1.5*d(A,B)+d(B,d1)+d(B,d2)

这个搜索是O(n ^ 2),所以整体成本是O(n ^ 2)+ O(n ^ 3)= O(n ^ 3)