1
$\begingroup$

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

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

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ fantastic solution! $\Theta(|V(G)|+|E(G)|)$ - as I see - the best way to find reachable vertices is with BFS..... $\endgroup$
    – Ami Gold
    Commented Jul 17, 2017 at 13:39
  • $\begingroup$ Either BFS or DFS. They have the same complexity. $\endgroup$
    – Fabio Somenzi
    Commented Jul 17, 2017 at 14:44
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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