1
$\begingroup$

There is an undirected graph and some of the vertices are said to be stores. Person A wants to reach to person B with a present. That means person A has to stop by one of the vertices marked as stores and get the present first before ever reaching to person B. Moreover, each store has a specific waiting time, and if the person decides to stop by at that particular supermarket, the waiting time should be included in the shortest path(shortest time).

Well, regular Dijkstra does not work very well because the shortest path may not include any store vertices, so the stores should somehow be incorporated in the algorithm. It is a must to visit one of the vertices marked as a store. But total travel time has to be the minimum.

Only the vertices marked as stores have weights, and it is a must to visit at least one of them.

$\endgroup$
1
$\begingroup$

You can do this with two instances of shortest paths.

  1. You need to know the shortest distance $d(A,S)$ for each store $S$. This is just Dijkstra from source $A$.

  2. You also need to know all the shortest paths from each store to B; i.e. $d(S,B)$ for each store $S$. This can be done by reversing the edges in the graph and running Dijkstra from source $B$.

Once you have these two, all you need to do is compute the min over paths that stop at a store, including the weight $w$ of the store.

$\min_S \left(d(A,S) + w(S) + d(S,B)\right)$

Asymptotically, in total, this is no more expensive than just running Dijkstra's algorithm. In practice you can stop early in each instance of Dijkstra once you've seen all of the stores.

$\endgroup$
  • $\begingroup$ Despite giving the correct answer, it is computationally expensive. Can you think of a faster way? $\endgroup$ – nmd_07 Nov 9 '18 at 9:40
  • $\begingroup$ Number of Dijkstras to be executed increases proportionally with number of stores. $\endgroup$ – nmd_07 Nov 9 '18 at 10:00
  • $\begingroup$ No, you only need to run Dijkstra twice, regardless of the number of stores. Dijkstra form source A computes the shortest paths from A to all stores. Dijkstra from source B on the reverse graph computes the shortest paths from all stores to B. $\endgroup$ – Sam Westrick Nov 9 '18 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.