扭曲的最短路径

Question

我有 n 个顶点和它们之间的 m 个无向加权边（权重代表分钟）。每个顶点包含在该顶点上喝咖啡所需的分钟数。

我想确定从顶点 v 到顶点 w 所需的最短时间（分钟），但有额外的限制，我必须在其中一个点喝咖啡从 v 到 w 的顶点。

示例：

（顶点的数字是喝一杯咖啡所需的分钟数，边上的权重代表走这条边所需的分钟数）

从v到w，路上喝杯咖啡，输出最少的必要时间（输出应该是30）。

我目前的做法是用Dijkstra求最短路径（求和该路径上所有边的权值）然后加上咖啡最低的顶点的值为了得到从 v 到 w.

所需的总时间

我的方法不行，这里是我的方法失败的例子（我的方法结果是12分钟，实际结果应该是6分钟）：

如何确定从顶点 v 到 w 的最短时间量以及我需要在我的路径上喝咖啡的约束？

Answer 1

我会尝试编写一个 A* 算法来解决这个问题。当你扩展一个节点时，你会为每个输出顶点得到两个子节点；一个你喝咖啡的地方，一个你不喝咖啡的地方。如果您使用 Dijkstra 的运行预处理您的算法（因此您已经预先计算了最短路径），那么您可以使用 Dijkstra 的最短路径 + 喝咖啡的最短时间（或者 + 0 如果咖啡已经 d运行k).

当您不仅到达目的地节点，而且喝完咖啡时，A* 搜索结束（您已达到目标）。

第二种情况的示例搜索：

Want: A --> C

A(10) -- 1 -- B(10) -- 1 -- C(10)
 \                           /
  \                         /
   2 -------- D(2) ------- 2   



Expand A
  A*(cost so far: 10, heuristic: 2)          total est cost: 12
  B (cost so far: 1, heuristic: 1 + 2)       total est cost: 3
  B*(cost so far: 11, heuristic: 1)          total est cost: 12
  D (cost so far: 2, heuristic: 2 + 2)       total est cost: 6
  D*(cost so far: 14, heuristic: 2)          total est cost: 16
  Expand B
    A*(cost so far: 12, heuristic: 2)        total est cost: 14
    B*(cost so far: 11, heuristic: 1)        total est cost: 12
    C(cost so far: 2, heuristic: 2)          total est cost: 4
    C*(cost so far: 12, heuristic: 0)        total est cost: 12
    Expand C
      B*(cost so far: 13, heuristic: 1)      total est cost: 14
      C*(cost so far: 12, heuristic: 0)      total est cost: 12
  Expand D
    A* (cost so far: 14, heuristic: 2)       total est cost: 16
    D* (cost so far: 4, heuristic: 2)        total est cost: 6
    C  (cost so far: 4, heuristic: 0 + 2)    total est cost: 6
    C* (cost so far: 6, heuristic: 0)        total est cost: 6
    Expand C*
       goal reached.                         total cost: 6

Key:
  * = Coffee from parent was drunk

所以你可以看到这个算法要做的是首先尝试沿着 Dijkstra 的最短路径走（永远不要喝咖啡）。然后当它到达终点时，它会看到一个物理目标状态，但仍然需要喝咖啡。当它扩展这个物理目标状态去喝咖啡时，它会发现到达成本不是最优的，所以它会从另一个分支继续搜索并继续。

请注意，在上面，A 和 A* 是不同的节点，因此您可以通过某种方式重新访问父节点（但前提是咖啡饮用状态不同）。这是为了解决这样的图表：

Want A-->B

A(20) -- 1 -- B(20)
  \
   2
    \
    C(1)

A->C->C*->A*->B* 的合理位置

我不确定我们是否需要区分 "coffee drank" 我们喝咖啡的节点的状态，但我倾向于不需要。

Answer 2

一种方法如下：

计算从 u 到所有其他顶点的最短路径并将其称为 p(u,x)
计算从所有顶点到v的最短路径并将其称为p(x,v)
遍历所有顶点并找到值的最小值 (p(u,x)+coffee(x)+p(x,v))

这样做会导致算法的时间复杂度与 Dijkstra 的算法相同（如果您在步骤 1 和 2 中使用 Dijkstra 的算法）

Answer 3

解决这个问题的标准方法是：

复制你的图表 2 份 -- need_coffee 版本和 had_coffee version.
将每个 need_coffee 节点与相应的 had_coffee 节点连接起来，边成本等于在该节点喝咖啡的成本。
用Dijkstra算法求出从V_need_coffee到W_had_coffee

扭曲的最短路径

Shortest path with a twist

java

algorithm

dijkstra

shortest-path

graph-algorithm