最短路径的变化版

Question

我有n个顶点和它们之间的m条带权无向边（权重表示分钟）。每个顶点包含一定数量的时间，需要在该顶点上喝咖啡。

我想确定从顶点v到顶点w所需的最短时间（以分钟为单位），但有一个额外的限制条件：我必须在从v到w的路上的某个顶点上喝咖啡。 示例：

（顶点中的数字是喝咖啡所需的分钟数，边上的权重表示行驶这条边所需的分钟数）

从v到w并在途中喝咖啡，输出最小所需时间（输出应为30）。

我的当前方法是使用Dijkstra算法找到最短路径（将该路径上所有边的权重相加），然后将该路径上咖啡时间最短的顶点的值添加到我的结果中，以便获得从v到w所需的总时间。

我的方法不起作用，这里有一个例子，我的方法失败了（我的方法的结果是12分钟，实际结果应该是6分钟）：

如何确定从顶点 v 到 w 的最短时间，但需要在路径上喝咖啡？

- PlsWork

---

这似乎是一个适合 https://math.stackexchange.com 的问题。 - benbants

这是我在一次编程面试中收到的问题。 - PlsWork

最好在问题中说明，但我仍认为这应该放在数学交换中。 - benbants

顶点“9”是否与图连接？ - AndyG

Answer 1

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

1. 复制你的图表两份——一个是“需要咖啡”版本，另一个是“已喝咖啡”版本。

2. 将每个“需要咖啡”节点与相应的“已喝咖啡”节点连接起来，边缘成本等于在该节点饮用咖啡的成本。

3. 使用Dijkstra算法找到从“V_need_coffee”到“W_had_coffee”的最短路径

- Matt Timmermans

---

这个问题有一个名称吗？我在哪里可以了解更多信息，也许可以找到更详细的描述来解决它的标准方法？ - PlsWork

不仅是这个问题，还有很多类似的问题需要您在其他条件下找到最短路径。我听说过这种技术被称为“图层”，但我不知道是否有标准名称。这里有一个关于它的好演讲：https://www.youtube.com/watch?v=OQ5jsbhAv_M&feature=youtu.be&t=47m7s - Matt Timmermans

你的算法解决方案总是那么深刻。 - AndyG

这个解决方案优雅、简单，对我很有效，只是我不明白你解决这个问题的方法和你提到的视频之间的联系是什么？ - PlsWork

该视频展示了使用相同的技术来解决“<= N跳的最短路径”问题。它同样适用于具有交替红+蓝边缘、至多N个特殊边缘的最短路径等等。 - Matt Timmermans

谢谢，我从你的解决方案中学到了很多。如果可以的话，我会点赞两次的。 - PlsWork

Answer 2

一种方法如下：

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

这样做将导致一个与Dijkstra算法具有相同时间复杂度的算法（如果在步骤1和2中使用Dijkstra算法）。

- Damien Prot

---

你对每个节点运行 Dijkstra 算法两次，复杂度不应该是 O(V * E * logV) 吗？ - PlsWork

Dijkstra算法能够计算从一个节点到所有其他节点的最短路径，请参阅维基页面以获取示例。 - Damien Prot

更准确地说，您可以查看https://en.wikipedia.org/wiki/Shortest_path_problem#Single-source_shortest_paths - Damien Prot

所以在第一步中，您的算法运行Dijkstra一次（确定从u到所有其他顶点的最短路径），在第二步中，您运行Dijkstra来确定从v到所有其他顶点的最短路径。在第三步中，您遍历所有节点并计算p（u，x）+coffee（x）+p（x，v），保存最小值并在最后输出它。总体而言，这将运行Dijkstra 2次，并遍历所有节点一次。我理解得对吗？ - PlsWork

是的，就是这样！ - Damien Prot

Answer 3

我会尝试编写一个A*算法来解决这个问题。当您扩展一个节点时，每个出边都会有两个子节点；一个是喝咖啡的，另一个是不喝咖啡的。如果您在算法中先运行Dijkstra算法（因此您已经预先计算了最短路径），那么您可以使用Dijkstra的最短路径+喝咖啡的最短时间（如果已经喝了咖啡，则为+0）来通知A*搜索的启发式函数。

当您不仅到达目标节点，而且还喝了咖啡时，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*的路径中，这种走法是有意义的。

我还不确定我们是否需要通过喝咖啡的节点来区分“喝掉的咖啡”状态，但我倾向于不需要。

- AndyG

---

有趣的方法，看起来不错（我想不出反例）。 - PlsWork