Shortest path with a twist

Question

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?

Answer 1

The standard way to solve this problem is:

1. make 2 copies of your graph -- the need_coffee version and the had_coffee version.

2. 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.

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

Answer 2

One way to do it is as following:

1. Compute the shortest path from u to all the other vertices and call it p(u,x)
2. Compute the shortest path from all the vertices to v and call it p(x,v)
3. loop over all vertices and find the minimum of the value (p(u,x)+coffee(x)+p(x,v))

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)