1
$\begingroup$

Given is a directed graph $G = (V, E)$ with positive edge weights $w:E \to \mathbb{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 \subseteq V$, and a function $s:A \to \mathbb{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 $\frac{w(e)}{s(v)}$ time-units to cross road $e$.

Suggest an efficient algorithm that returns the winner(s).

My attempt:

Algorithm:

  1. Run Dijkstra on some node $v \in A$, and initiate an array of size $|A|$ (for each player).
  2. For each $v \in A$, iterate through a shortest path from $v$ to $t$, and in each iteration add $\frac{w(e)}{s(v)}$ to the sum of this specific node in the array.
  3. 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!

$\endgroup$

1 Answer 1

0
$\begingroup$

Instead of running Dijkstra's algorithm for some $v \in A$, how about we run Dijkstra's Algorithm for all $v \in A$?

The result is, $\forall v \in A$, we have the shortest distance (minimum weight) from node $v$ to node $t$.

We store in an array, the minimum distance of each player, divided by that player's speed. In other words, we store the time taken to reach the prize. Then we just find the minimum in that array.

However, I think you understand the previous paragraph. What you missed is that Dijkstra's algorithm already gives us the minimum distance (minimum weight) path from $v$ to $t$. In your step 2, I'm not sure what you are trying to do with the extra iterations.

$\endgroup$
3
  • $\begingroup$ In case of $A=V$, the running time will be at least $O(n^2)$, which is not good... $\endgroup$
    – Math4Me
    Commented Nov 12, 2021 at 8:59
  • 1
    $\begingroup$ You can reverse the edges of the graph and run Dijkstra from $t$. This will give you a shortest path from $v$ to $t$, for every vertex $v$, in one iteration. $\endgroup$
    – Dániel G.
    Commented Nov 12, 2021 at 16:01
  • $\begingroup$ @DánielG. wow I have never thought of that, nice $\endgroup$ Commented Nov 12, 2021 at 16:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .