Another common problem is to find the shortest pairs within a graph. An algorithm from Floyd is explained.
The best solution is to use a matrix for implementation. If a node does not have a direction connection to another node the cost is unlimited. The algorithm looks at the successors and predecessor. If one of the successors is not connected with a predecessor then a new edge between them is created and the cost of the connection is added in the matrix.
The runtime is O(n^3).
Sometimes the cost between nodes does not matter, in this case one speaks of the "transitive closure".
A directed Graph can contain strong components There are four steps needed to extract the strong components. 1: Run a Depth-First-Algorithm. 2: Inverse the direction of the edges 3: Run a Depth-First-Algorithm 4: Combine the results of Step 1 and 3.