com.mhhe.clrs2e
Class AllPairsShortestPaths

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

Direct Known Subclasses:

APSPMatrixMult, FloydWarshall

public abstract class AllPairsShortestPaths

extends java.lang.Object

Abstract class for computing all-pairs shortest paths.

Constructor Summary

AllPairsShortestPaths()

Method Summary

abstract double[][]	computeShortestPaths(com.mhhe.clrs2e.WeightedAdjacencyMatrixGraph g) Computes all-pairs shortest paths.
protected double[][]	graphToMatrix(com.mhhe.clrs2e.WeightedAdjacencyMatrixGraph g) Converts a WeightedAdjacencyMatrixGraph to a matrix of edge weights.
static void	printMatrix(boolean[][] matrix) Prints out a 2-dimensional array of boolean as 0s and 1s.
static void	printMatrix(double[][] matrix) Prints out a 2-dimensional array of double.

Methods inherited from class java.lang.Object

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

Constructor Detail

AllPairsShortestPaths

public AllPairsShortestPaths()

Method Detail

computeShortestPaths

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

Computes all-pairs shortest paths.

Parameters:

g - A weighted graph represented as an adjacency matrix.

Returns:

A matrix of shortest-path weights.

graphToMatrix

protected double[][] graphToMatrix(com.mhhe.clrs2e.WeightedAdjacencyMatrixGraph g)

Converts a WeightedAdjacencyMatrixGraph to a matrix of edge weights.

Parameters:

g - A weighted graph represented as an adjacency matrix.

Returns:

A matrix of edge weights. Regardless of what the adjacency matrix has along the diagonal, the returned matrix has all zeros along the diagonal.

printMatrix

public static void printMatrix(double[][] matrix)

Prints out a 2-dimensional array of double.

Parameters:

matrix - The array to print.

printMatrix

public static void printMatrix(boolean[][] matrix)

Prints out a 2-dimensional array of boolean as 0s and 1s.

Parameters:

matrix - The array to print.