Clever Geek Handbook

Shortest way with a turn

I have n

vertices and m

undirected weighted edges in between (the scales represent minutes). Each peak contains a few minutes to drink coffee at that peak.

I want to define the shortest amount of time (minutes) it takes to get from top v

to top w

, but with the added restriction that I have to drink my coffee at one of the peaks on my way from v

to w

).

Example :

(the number at the top is the number of minutes it takes to drink coffee, the weights at the edges represent the number of minutes it takes to move that edge)

Get from v

to w

and have coffee on your way, output the minimum time required (exit should be 30).

enter image description here

My current approach is to find the shortest path using Dijkstra (sum the weights of all edges along the way) and then add the value of the vertex with the lowest coffee time along the way to my result to get the total amount of time it takes to go from v

to w

.

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

Counterexample for my approach

How do I determine the shortest time span from the top v

to w

with the restriction that I need to drink coffee on my way?

+3


source to share


3 answers


The standard way to solve this problem is:



  • make 2 copies of your schedule - version need_coffee

    and had_coffee version

    .

  • Connect each need_coffee

    node to the corresponding had_coffee

    node, with the cost of the edge equal to the cost of drinking coffee with that node.

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

    toW_had_coffee

+7


source


I would try to write an A * algorithm to solve this problem. When you expand a node, you get two children for each outgoing vertex; where you drink coffee and the other where you don't. If you envision your algorithm running Dijkstra (so that you already have pre-computed shortest paths), you can tell the search heuristic A * with the shortest path Dijkstra + minimum time to drink coffee (or + 0 if coffee has already been drunk).

The A * search ends (you have reached your goal) when you have arrived not only at the destination node, but also drank your coffee.

An example of finding the second script:

Want: A --> C

A(10) -- 1 -- B(10) -- 1 -- C(10)
 \                           /
  \                         /
   2 -------- D(2) ------- 2   



Expand A
  A*(cost so far: 10, heuristic: 2)          total est cost: 12
  B (cost so far: 1, heuristic: 1 + 2)       total est cost: 3
  B*(cost so far: 11, heuristic: 1)          total est cost: 12
  D (cost so far: 2, heuristic: 2 + 2)       total est cost: 6
  D*(cost so far: 14, heuristic: 2)          total est cost: 16
  Expand B
    A*(cost so far: 12, heuristic: 2)        total est cost: 14
    B*(cost so far: 11, heuristic: 1)        total est cost: 12
    C(cost so far: 2, heuristic: 2)          total est cost: 4
    C*(cost so far: 12, heuristic: 0)        total est cost: 12
    Expand C
      B*(cost so far: 13, heuristic: 1)      total est cost: 14
      C*(cost so far: 12, heuristic: 0)      total est cost: 12
  Expand D
    A* (cost so far: 14, heuristic: 2)       total est cost: 16
    D* (cost so far: 4, heuristic: 2)        total est cost: 6
    C  (cost so far: 4, heuristic: 0 + 2)    total est cost: 6
    C* (cost so far: 6, heuristic: 0)        total est cost: 6
    Expand C*
       goal reached.                         total cost: 6

Key:
  * = Coffee from parent was drunk

So you can see that this algorithm will first try to go down Dijkstra's shortest path (never drink coffee). And then, when he reaches the goal, he will see the state of the physical goal, but with the need to drink more coffee. When he expands this physical state of the target to drink coffee, he will see that the cost of arrival is sub-optimal, so he continues searching from another branch and continues.



Note that in the above case, A and A * are different nodes, so somehow you can go back to the parent node (but only if the coffee consumption state is different). This applies to the graph as follows:

Want A-->B

A(20) -- 1 -- B(20)
  \
   2
    \
    C(1)

Where would it be appropriate to go from A-> C-> C * → A * → B *

I'm not sure yet if we need to distinguish between the "drunk coffees" in which node we drank coffee, but I'm leaning towards no.

+1


source


One way to do it:

  • Calculate the shortest path from u to all other vertices and call it p (u, x)
  • Compute the shortest path from all vertices in v and call it p (x, v)
  • iterate over all the vertices and find the minimum value (p (u, x) + coffee (x) + p (x, v))

This will result in an algorithm with the same time complexity as Dijkstra one (if you use Dijkstra's algorithm in steps 1 and 2)

+1


source






More articles:


All Articles