Think About It

Ask yourself:

$1.$ Can you use BFS for longest path? Why or why not?

$2.$ Why does DP on DAGs work here?

$3.$ How do you process nodes in the right order to compute longest paths? Next unit connects this to DP on DAGs.

BFS finds shortest paths, not longest. Dijkstra also minimizes, not maximizes. For longest paths in a DAG, process nodes in topological order. At each node, check all incoming edges and take the maximum distance plus one. This works because topological order guarantees all predecessors are processed before each node.