com.mhhe.clrs2e
Class FloydWarshall

java.lang.Object
  |
  +--com.mhhe.clrs2e.AllPairsShortestPaths
        |
        +--com.mhhe.clrs2e.FloydWarshall

public class FloydWarshall

extends AllPairsShortestPaths

Implements the Floyd-Warshall algorithm for all-pairs shortest paths from page 630 and the Transitive-Closure algorithm from page 633 of Introduction to Algorithms, Second edition.

Constructor Summary

FloydWarshall()

Method Summary

double[][]	computeShortestPaths(com.mhhe.clrs2e.WeightedAdjacencyMatrixGraph g) Computes all-pairs shortest paths.
boolean[][]	computeTransitiveClosure(com.mhhe.clrs2e.AdjacencyMatrixGraph g) Computes the transitive closure of a directed graph.

Methods inherited from class com.mhhe.clrs2e.AllPairsShortestPaths

graphToMatrix, printMatrix, printMatrix

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

FloydWarshall

public FloydWarshall()

Method Detail

computeShortestPaths

public double[][] computeShortestPaths(com.mhhe.clrs2e.WeightedAdjacencyMatrixGraph g)

Computes all-pairs shortest paths.

Specified by:

computeShortestPaths in class AllPairsShortestPaths

Parameters:

g - A weighted graph represented as an adjacency matrix.

Returns:

A matrix of shortest-path weights.

computeTransitiveClosure

public boolean[][] computeTransitiveClosure(com.mhhe.clrs2e.AdjacencyMatrixGraph g)

Computes the transitive closure of a directed graph.

Parameters:

g - A graph represented as an adjacency matrix.

Returns:

A transitive-closure matrix in which the [i][j] entry is true if there is a path from vertex i to vertex j, false otherwise.