Provide the best algorithm for finding the shortest path in given Graph

I've been struggling with a question - Not sure if I found the best algorithm possible. Would appreciate your suggestions!

 The question: Given directed graph G=(V,E), suppose V={1,2,...,n} (i.e. vertices are numbered between 1 and n). Let's mark with R(v) the group of vertices that are reachable from the vertex v with a directed path in G. Let's mark r(v) to be the minimal vertex in R(v). (r(v) vertex has the minimal number in the group R(v)). Provide algorithm that finds for each vertex v in V(G) the r(v). 

What I did is a reduction to an algorithm based on Dijkstra. At first, I turned all the numbered vertices into sets of 2 vertices - so every vertex u would be represented as $u_{in}$ and $u_{out}$ and an edge between $u_{in}$ and $u_{out}$ with a weight that is represented as the number of u.

Meaning, an edge from v to x will now pass from $v_{out}$ to $x_{in}$ and it's weight would be 0. while the edge between $v_{in}$ and $v_{out}$ would weight as the number represented v.

IN THIS WAY, I need to run Dijkstra algorithm n times for |V(G)| vertices - is there a better solution??

• Consider the graph $3 \rightarrow 2 \rightarrow 1$. What solution does your modified Dijkstra algorithm produce, and what do you expect? Commented Jul 17, 2017 at 13:13

• fantastic solution! $\Theta(|V(G)|+|E(G)|)$ - as I see - the best way to find reachable vertices is with BFS..... Commented Jul 17, 2017 at 13:39
I would run a depth-first search from all starting vertex $v$ and maintain the list of all vertices encountered during the search. This would generate the set $R(v)$. At the end, find the minimum element of $R(v)$. For a specific $v$ this would take $\underbrace{O(V+E)}_{DFS} +\underbrace{O(V)}_{min\ search} = O(V+E)$. Then doing that from all starting $v$, this would take $O(V(V+E))$. This is better than running Dijkstra on every starting $v$, which would take $O(V(E + V\log V))$