扭曲的最短路径

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

我想确定从顶点v到顶点w所需的最短时间（分钟），但是我必须在从v到w路上的一个顶点上喝咖啡。

示例 ：

（顶点中的数字是喝咖啡所需的分钟数，边缘上的重量表示行进此边缘所需的分钟数）

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

我目前的方法是找到Dijkstra的最短路径（总结该路径上所有边的权重），然后将该路径上具有最低咖啡时间的顶点值添加到我的结果中，以获得总量从v到w必要时间。

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

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

Answer 1

解决此问题的标准方法是：

1. 制作2个图表副本 – need_coffee版本和had_coffee version 。

2. 将每个need_coffee节点与相应的had_coffee节点连接，其边缘成本等于在该节点上喝咖啡的成本。

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

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算法）

Answer 3

我会尝试写一个A *算法来解决这个问题。 展开节点时，每个传出顶点都会有两个子节点; 一个你喝咖啡的地方，另一个你不喝咖啡的地方。 如果您使用Dijkstra的运行预先调整算法（因此您已经有预先计算的最短路径），那么您可以通过Dijkstra的最短路径+最小时间喝咖啡来通知A *搜索的启发式（如果咖啡已经喝醉，则为+ 0） 。

当您不仅到达目的地节点，而且还喝了咖啡时，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 *有意义的地方

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