All Pairs shortest Path

Posted in Data structure by

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 , Updated at 2011-10-25

next: Minimal Spanning Tree prev: Single Source Shortest Path