# Difference between revisions of "DAG Longest Path"

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: | ||

− | + | ||

+ | |||

+ | 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 | + | |

+ | 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.