# modify dfs to find longest path

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. How can i modify the above algorithm to find the u.dist value correctly for each node u.

• this algorithm seems very specific, can you reference your source?
– lox
Nov 29, 2021 at 10:04

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.