一种最短路径算法的变体

Question

我们有一个带有两个源点和两个目标点（分别为s1、s2、d1、d2）的加权无向图。从源点1到目标点1和从源点2到目标点2的费用定义如下：

• 如果仅使用边，则使用边的成本等于其权重。
• 如果两个路径都使用该边，则使用边的成本等于其权重的1.5倍（即s1->..->d1和s2->..->d2）。

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

如果路径使用具有相反方向的边，则不会减少成本。

请提供任何有关确定最小化总成本算法的帮助、思路或建议？

- stationary traveller

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)。

- Peter de Rivaz

---

应该是...+d(B,d1)+d(B,d2)，而不是s1/s2。 - abraabra

为什么最短的部分共享路径不能在共享子路径和非共享子路径之间交替出现？因为如果这样发生了，那么根据我的理解，就无法找到那种类型的路径。 - G. Bach

假设最短路径是共享的A->B，然后不共享的B->C，然后共享的C->D。考虑两个未共享的路线B->C。假设人1的成本为x，人2的成本为y。让速度较慢的人沿着与速度较快者相同的路线走，总是更好的选择。采用共享路线的成本将为1.5(min(x,y))，这永远不会比x+y更糟糕。 - Peter de Rivaz

Answer 2

@Peter de Rivaz提供了一种基于Floyd算法的运行时间为O(n^3)的解决方案。以下替代方案基于Dijkstra算法，运行时间为O(n^4)，但可能适用于更一般的问题设置（请参见附录）：

生成一个新图，其中有n^2个节点，图中的每个节点(a, b)对应于原始图中两个节点a和b的组合。这个新图的节点连接如下：如果：

• 从a到c存在一条边或者a==b，并且
• 从b到d存在一条边或者b==d

则在(a, b)和(c, d)之间存在一条边。

在原始图中，这条新边的成本对应于原始图中两条边的和，除非a = b和c = d，此时成本为原始边的和乘以1.5。

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

补充：

基于Floyd的方法的主要优点是，在修改问题陈述方面具有更大的灵活性。例如，可以解决问题变体，其中“共享折扣”仅在两个旅行者在同一“步骤”中共享边缘时授予：您只需要相应地调整权重即可。

- blubb