Difference between revisions of "DAG Longest Path"

From visone manual
Jump to navigation Jump to search
(Created page with "The input must be a directed acyclic graph (DAG). A source in DAG is a node which has only outgoing links. Each node gets the length of the longest directed path from any source ...")
 
Line 1: Line 1:
The input must be a directed acyclic graph (DAG).
+
 
 +
 
 +
Each node gets the length of the longest directed path from any source in the directed acyclic graph (DAG).
 
A source in DAG is a node which has only outgoing links.
 
A source in DAG is a node which has only outgoing links.
Each node gets the length of the longest directed path from any source in the DAG.
+
 
 +
If the graph has cycles, each strongly connected component is aggregated to one vertex which results in a DAG.
 +
Each vertex gets the longest directed path from any strongly connected component which has not incoming edges from any other strongly connected component.

Revision as of 08:14, 7 August 2015


Each node gets the length of the longest directed path from any source in the directed acyclic graph (DAG). A source in DAG is a node which has only outgoing links.

If the graph has cycles, each strongly connected component is aggregated to one vertex which results in a DAG. Each vertex gets the longest directed path from any strongly connected component which has not incoming edges from any other strongly connected component.