1
$\begingroup$

In Tarjan's algorithm for finding SCC/AP/Bridges, we update the value of the low[u] to be the min ( low[u], desc[v] ) given that v is a neighbor and has been discovered before, why it's not like this instead low[u] = min(low[u], low[v])?

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! 1. This is unanswerable without looking at the specific version of Tarjan's algorithm you're looking at (e.g., the specific pseudocode you have in front of you). What's low[u]? desc[v]? I'm sure it's well-defined in the copy of the pseudocode you have, but others might have learned Tarjan's algorithm with pseudocode that uses different variable names. $\endgroup$ – D.W. Aug 20 '16 at 17:11
  • $\begingroup$ 2. What have you tried? Have you tried working through some small examples to see what happens if you use your proposed modification? Does it always give the right answer on all the examples you tried? Have you tried working through the proof of correctness for Tarjan's algorithm to see if you can modify it to prove your variant correct, or see which step it breaks down at? If you can address this feedback, edit your question accordingly and it can be considered for re-opening. $\endgroup$ – D.W. Aug 20 '16 at 17:12
  • $\begingroup$ I've seen the algorithm in this link here, and the question also appears in the same topic in this link geeksforgeeks.org/… $\endgroup$ – Kareem Aug 20 '16 at 17:49