我们得到一个带两个源和两个目标顶点(比如 s1、s2、d1、d2)的加权无向图。 从源 1 到目的地 1 和源 2 到目的地 2 的成本定义为:
- 如果仅使用两条路径中的一条，则使用一条边的成本等于权重。
- 如果两条路径都使用边(s1->..->d1 和 s2->..->d2)，则使用边的成本等于权重的 1.5 倍。
总之，如果两条路径使用同一条边，则总成本增加“1.5 x 权重”而不是“2 x 权重”。鼓励使用公共(public)边。
如果路径使用方向相反的边，则不会降低成本。
在确定最小化总成本的算法方面有任何帮助、想法或建议吗？
最佳答案
我建议首先使用 Floyd Warshall 找到所有对的最短路径在时间 O(n^3) 中，n 是顶点数。
一旦你有了它，你就可以计算沿着最短路径走 s1->d1 和 s2->d2 的成本，这给了你成本的上限。
做得更好的唯一方法是使用共享路径。如果是这样，那么s1和s2会在一个顶点A处汇合，然后沿着一条共享路径到达一个顶点B，然后 split 到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)
关于algorithm - 最短路径算法的变体，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22026691/