我们给定一个带权无向图，具有两个源顶点和两个目标顶点（例如 s1、s2、d1、d2）。
对于从源 1 到目的地 1 以及从源 2 到目的地 2 的成本定义为：
- 如果仅使用两条路径之一，则使用一条边的成本等于权重。
- 如果两条路径（s1->..->d1 和 s2->..->d2）都使用该边，则使用该边的成本等于权重的 1.5 倍。
总之，如果两条路径使用相同的边，则总成本会增加“1.5 x 权重”而不是“2 x 权重”。鼓励使用公共边缘。
如果路径使用方向相反的边，则不会降低成本。
对于确定最小化总成本的算法有什么帮助、想法或建议吗？
我建议首先使用以下方法找到所有对的最短路径弗洛伊德·沃歇尔 http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm时间为 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)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
