扭曲的最短路径 [英] Shortest path with a twist

问题描述

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

I have n vertices and m undirected weighted edges between them (weights are representing minutes). Each vertex contains a number of minutes required to drink a coffee on that vertex.

我想确定从顶点 v 到顶点<$所需的最短时间（分钟） c $ c> w 但是附加限制条件是我必须在从 v 到<的路上的一个顶点上喝咖啡。 code> w ）。

I want to determine the shortest amount of time (minutes) neccessary to get from vertex v to vertex w but with the additional constraint that I have to drink my coffee on exactly one of the vertices on my way from v to w).

示例：

（顶点的数字是喝咖啡所需的分钟数，边缘的重量代表了这个边缘所需的分钟数）

(number in the vertex is the amount of minutes required to drink a coffee, the weights on the edges represent the amount of minutes neccessary to travel this edge)

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

Get from v to w and drink a coffe on your way, output the minimal neccessary time (output should be 30).

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

My current approach is to find the shortest path with Dijkstra (sum up the weights of all edges on that path) and then add the value of the vertex with the lowest coffee time on that path to my result in order to get the total amount of time neccessary to get from v to w.

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

My approach doesn't work, here is an example where my approach fails (the result of my approach is 12 minutes, the actual result should be 6 minutes) :

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

How to determine the shortest amount of time from vertex v to w with the constraint that I need to drink a coffe on my path?

推荐答案

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

The standard way to solve this problem is:

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

连接每个 need_coffee 节点使用相应的 had_coffee 节点，边缘成本等于在该节点喝咖啡的成本。

Connect each need_coffee node with the corresponding had_coffee node, with an edge cost equal to the cost of drinking coffee at that node.

使用Dijkstra算法查找从 V_need_coffee 到 W_had_coffee

Use Dijkstra's algorithm to find the shortest path from V_need_coffee to W_had_coffee

这篇关于扭曲的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！