我有 n 个顶点和它们之间的 m 个无向加权边(权重代表分钟)。每个顶点包含在该顶点上喝咖啡所需的分钟数。
我想确定从顶点 v 到顶点 w 所需的最短时间(分钟)，但有额外的限制，我必须喝咖啡在我从 v 到 w 的过程中的一个顶点上。
示例:
(顶点的数字是喝一杯咖啡所需的分钟数，边上的权重代表通过这条边所需的分钟数)
从 v 到 w 并在途中喝咖啡，输出最小的必要时间(输出应为 30)。
我目前的方法是用 Dijkstra 找到最短路径(求和该路径上所有边的权重)，然后将该路径上咖啡时间最短的顶点的值添加到我的结果是为了获得从 v 到 w 所需的总时间。
我的方法不行，下面是我的方法失败的例子(我的方法结果是12分钟，实际结果应该是6分钟):
如何确定从顶点 v 到 w 的最短时间量以及我需要在我的路径上喝咖啡的约束？
最佳答案
解决这个问题的标准方法是:
为您的图表制作 2 个副本 --
need_coffee版本和had_coffee 版本。将每个
need_coffee节点与相应的had_coffee节点连接起来，边成本等于在该节点喝咖啡的成本。使用 Dijkstra 算法找到从
的最短路径V_need_coffee到W_had_coffee
关于java - 扭曲的最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44133138/