com.mhhe.clrs2e
Class FasterAllPairsShortestPaths

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

public class FasterAllPairsShortestPaths

extends APSPMatrixMult

Implements the Faster-All-Pairs-Shortest-Paths procedure on page 627 of Introduction to Algorithms, Second edition.

Constructor Summary

FasterAllPairsShortestPaths()

Method Summary

double[][]

computeShortestPaths(com.mhhe.clrs2e.WeightedAdjacencyMatrixGraph g) Computes all-pairs shortest paths.

Methods inherited from class com.mhhe.clrs2e.APSPMatrixMult

extendShortestPaths

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

FasterAllPairsShortestPaths

public FasterAllPairsShortestPaths()

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.