algorithm - 保留直接连接的最短路径算法？

Question

我想估计图中不直接相连的顶点之间的距离。

除了保留现有的直接连接外，是否有一种算法可以像 Dijkstra 的算法一样工作？

假设以下示例:

   (A)
 1/   \
(B)    |
1|     |5
(C)    |
 1\   /
   (D)

Dijkstra 算法会将节点 (A) 和 (D) 之间的距离设置为 3，而我希望尊重现有的直接连接并将距离设置为 5。我尝试使用未加权的距离在 scipy 的实现中没有任何运气。问题在于选择跳跃次数较少但总距离较长的路径而不是距离较短且跳跃次数较多的路径:

   (A)
 1/   \5
(B)    |
1|    (E)
(C)    |
 1\   /5
   (D) 

在这种情况下，我希望使用 (A) -> (B) -> (C) -> (D)，但未加权的 Dijkstra 更喜欢 (A) -> (E) -> (D) .

Answer 1

您可以使用 Dijkstra 来做到这一点。您只需要修改成本函数。您可以定义自己的结合它们的距离或跳跃测量，而不是单一的距离或跳跃测量。

当您选择一个节点作为迄今为止的最佳路径候选者时，您可以存储到达该节点所需的跳数。这很容易，因为您知道在您到达的节点上存储了多少跃点。

然后成本函数由您决定。您可能希望每一跳都受到 2 的惩罚。因此您可以说从节点 P 到达节点 Q 的成本是:

Cost(P,Q) = (Hops(P)+1) * 2 + Dist(P,Q)

正如 Tim 在评论中指出的那样，这实际上相当于将所有路径权重加 2，而无需任何额外编码。