This is the same as finding the critical path.
There's an easy O(n) DP solution:
- Topologically sort the vertices.
- For each vertex
i
we will recordearliest(i)
, the earliest possible start time (initially 0 for all vertices). Process each vertexi
in topologically-sorted order, updating (increasing)earliest(j)
for any successor vertexj
ofi
wheneverearliest(i) + length(i, j) > earliest(j)
.
After this is done, the maximum value of earliest(i)
over all vertices will be the length of the critical path (longest path). You can construct a (there may in general be more than one) longest path by tracing backwards from this vertex, looking at its predecessors to see which of them could have produced it as a successor (i.e. which of them have earliest(i) + length(i, j) == earliest(j)
), iterating until you hit a vertex with no predecessors.