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.
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
).
Example:
(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)
Get from v
to w
and drink a coffe on your way, output the minimal neccessary time (output should be 30).
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
.
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) :
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:
make 2 copies of your graph -- the need_coffee
version and the had_coffee version
.
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.
Use Dijkstra's algorithm to find the shortest path from V_need_coffee
to W_had_coffee
One way to do it is as following:
Doing so will lead to an algorithm with the same time complexity than Dijkstra's one (if you use Dijkstra's algorithm in step 1 and 2)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With