Difference between revisions of "DAG Longest Path"

From visone manual
Jump to navigation Jump to search
Line 1: Line 1:
 
 
 
Each node gets the length of the longest directed path from any source in the 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.

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.