Given is a directed graph G = (V, E) with positive edge weights w:E to R .
The graph represents roads in Brooklyn, and the weight on each edge indicates the length of the road in miles. A prize is placed in node t (in V). Given is a set of nodes A in V (A is a subset of V), and a function s:A to R .
In each v in A there is a player. In the beginning of the game, all the players depart simultaneously and proceed towards the prize.
Every player proceeds in a shortest path from its origin node to t. The player that departs from node v proceeds at a constant speed s(v), i.e., for every e in E, it takes this player w(e)/s(v) time-units to cross road e.
Suggest an efficient algorithm that returns the winner(s).
My attempt:
Algorithm:
- Run Dijkstra on some node v in A, and initiate an array of size |A| (for each player).
- For each v in A, iterate through a shortest path from v to t, and in each iteration add w(e)/s(v) to the sum of this specific node in the array.
- Return the minimum of the array.
I think this can be improved, for example replace the array with other data structure which will make the last step more efficient, but I do not know how.
I will appreciate any help!
Thanks!
CodePudding user response：
You can do this by running Dijkstra's algorithm once from the destination node t to compute all shortest paths to/from t. You're looking for the minimum, over all a ∈ A, of Distance(a, t) / Speed(a), where Distance is the standard sum-of-edge-weights from Dijkstra's algorithm. Since the original graph is directed, you'll need to reverse the direction of all edges first and work on that graph.
If 'A' is small, you can occasionally optimize this slightly by stopping Dijkstra's algorithm as soon as you've visited all of the nodes in A, although the worst-case runtime is the same.