最短路径算法的变体

2018-05-31 02:14:06

给出一个带有两个源和两个目标顶点（称为s1，s2，d1，d2）的加权无向图。对于从源1到目的地1和源2到目的地2的成本定义为：

如果仅使用两条路径中的一条，则使用边的成本等于重量。

如果边缘同时使用两条路径（s1→d→d1和s2→d→d2），则使用边的成本等于重量的1.5倍。

总之，如果两条路径使用相同的边缘，则总成本将增加“1.5倍重量”而不是“2倍重量”。鼓励使用共同的边缘。

如果路径使用反方向的边，则不会降低成本。

任何帮助，想法或建议，以确定一个最小化总成本的算法？

我建议首先在时间O（n ^ 3）中找到使用Floyd Warshall的所有对最短路径，其中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）

@Peter de Rivaz提供了一个基于Floyd算法在O(n^3)中运行的解决方案。下面的选择是基于Dijkstra的算法，并且运行在O(n^4) ，但可能适用于更一般的问题设置（参见附录）：

用n^2节点生成一个新图，其中图中的每个节点(a, b)对应于原始图中两个节点a和b的组合。这个新图的节点连接如下：在(a, b)和(c, d)之间存在边iff：

有从a到c或a == b ，并且

有从b到d或b == d的边缘

在原始图中。这个新边的成本对应于原始图中两个边的总和，除非a = b和c = d ，在这种情况下，成本是原始边的总和乘以1.5。

这个新图形还包括两个节点(s1, s2)和(d1, d2) 。简单地确定这两个节点之间的最短路径，并且可以轻松推导出原始图形中的各个路径。

附录：

基于Floyd的方法的主要优点是您可以在修改问题陈述方面获得更多的灵活性。例如，如果两个旅行者在同一个“步骤”中共享边缘，只能获得“共享折扣”，则可以解决问题的变化：您需要做的就是相应调整重量。

链接地址: http://www.djcxy.com/p/6007.html