##
All Pairs shortest Path

Posted in Data structure by #care-crew

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.

Published at 2011-10-25, Updated at 2011-10-25

next: Minimal Spanning Tree
prev: Single Source Shortest Path