Longest Path in a Graph: Difference between revisions
Jump to navigation
Jump to search
| (2 intermediate revisions by the same user not shown) | |||
| Line 12: | Line 12: | ||
Topologically sort the directed acyclic graph: | Topologically sort the directed acyclic graph: | ||
{{Internal|Topological_Sort_of_a_Directed_Acyclic_Graph#Overview|Topological Sort of a Directed Acyclic Graph}} | {{Internal|Topological_Sort_of_a_Directed_Acyclic_Graph#Overview|Topological Sort of a Directed Acyclic Graph}} | ||
Then <font color=darkkhaki>TODO: https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph</font>. | |||
Latest revision as of 04:45, 9 November 2021
External
- https://en.wikipedia.org/wiki/Longest_path_problem
- https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/
Internal
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:
Then TODO: https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph.