DAG Longest Path: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| 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. | ||
If the graph has cycles, each strongly connected component is aggregated to one | If the graph has cycles, each strongly connected component is aggregated to one node which results in a DAG. | ||
In this case, each vertex gets the longest directed path from any strongly connected component whose nodes do not have any incoming edge to a node of another strongly connected component. | |||
Latest revision as of 08:16, 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 node which results in a DAG. In this case, each vertex gets the longest directed path from any strongly connected component whose nodes do not have any incoming edge to a node of another strongly connected component.