扭曲的最短路径

Question

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

我想确定时间(分钟)neccessary的最短摆脱顶点v到顶点w但是我必须喝顶点恰好我的一个咖啡对我的方式从另外的约束v来w).

示例:

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

从获取v到w和喝咖啡对你的方式,输出的最小留点时间(输出应为30).

我目前的方法是找到Dijkstra的最短路径(总结该路径上所有边的权重),然后将该路径上具有最低咖啡时间的顶点值添加到我的结果中,以获得总量时间neccessary从中获取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