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

Question

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??

Answer 1

Starting from vertex 1, find all vertices backward reachable from it. Then find the lowest-numbered vertex that hasn't been visited yet. Start another backward search from it. Continue until all vertices have been visited. No edge is examined more than once.

Answer 2

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))$