0
$\begingroup$

Let $G = (V, E)$ be a directed acyclic graph. Let every node $v \in V$ have an additional field $v_d$.

For each vertex $v \in V$, we need to store in $v_d$ the length of the longest path in $G$ that begins at $v$. The length of a path is given by the number of edges on this path.

enter image description here

How can i modify the above algorithm to find the u.dist value correctly for each node u.

$\endgroup$
1
  • 2
    $\begingroup$ this algorithm seems very specific, can you reference your source? $\endgroup$
    – lox
    Commented Nov 29, 2021 at 10:04

1 Answer 1

0
$\begingroup$

I'm not going to tell you the exact modifications you need to do to the pseudo-code, but here is the high-level idea, which also shows why the longest-path problem on DAGs can be solved with just a DFS visit.

Forget about the visit for a second and suppose that you somehow know a topological order of the vertices of the graph. Let this order be $v_1, v_2, \dots, v_n$. Let $\ell(v_i)$ be the length of the longest path starting from $v_i$.

If $v_i$ is a sink we clearly have $\ell(v_i) = 0$. Otherwise: $$ \ell(v_i) = 1 + \max_{v_j \, : \, (v_i, v_j) \in E} \ell(v_j). $$

Notice that, due to our topological order, we necessarily have that $j>i$ in the above formula. This means that we are always able to compute $\ell(v_i)$ if we consider the vertices $v_i$ in reverse topological order.

This is where the above dynamic-programming algorithm connects with the DFS visit: if you consider the order of the vertices induced by the ending times of DFS visit, you obtain a reverse topological order of $G$, which is exactly what you need. This means that you can compute $\ell(v_i)$ just before the DFS visit on node $v_i$ ends.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.