Longest Path in a Graph

External

• https://en.wikipedia.org/wiki/Longest_path_problem
• https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

Internal

• Graphs

Overview

The longest path problem is an NP-Hard problem for general graphs. However, the longest path can be computed on O(n) time for directed acyclic graphs.

Longest Path in a Directed Acyclic Graph

Topologically sort the directed acyclic graph:

Topological Sort of a Directed Acyclic Graph

Then:

 initialize dist[n] = {MIN_VALUE, ..., MIN_VALUE}