# Algorithm using Dijkstra to calculate shortest path of a weighted graph

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!

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$$.
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.
• In case of $A=V$, the running time will be at least $O(n^2)$, which is not good... Commented Nov 12, 2021 at 8:59
• 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. Commented Nov 12, 2021 at 16:01