bcds.phison.alg
Class FloydWarshall<V,E>

java.lang.Object
  bcds.phison.ra.RoutingAlgBase<V,E>
      bcds.phison.alg.FloydWarshall<V,E>

public class FloydWarshall<V,E>
extends RoutingAlgBase<V,E>

Implements the Floyd-Warshall algorithm for finding all-pairs shortest paths in a graph. This is an adaptation of the code (in Python) found in https://networkx.lanl.gov/wiki

FloydWarshall does not implement the RoutingAlg interface and in fact it is quite unlike other routing algorithms in this package, for example, DijkstraAll:

• FloydWarshall finds all the shortest paths during the first call to run(). Successive calls only returns what has been computed during the first call.
• As a consequence of the previous point, the residual capacity is consulted only once (during the first call to run). Therefore, it insenstive to variations in residual capacity occuring between different calls to run.

The link cost used for determining shortest paths is what TED.getCost(E) returns for each link.

Beware: The execution time is in O(N^3) and the memory required is in O(N^2), where N = number of nodes.

Constructor Summary

FloydWarshall(TED<V,E> ted)
Creates a new instance and saves the ted parameter for future use.

Method Summary

double	getCost(V src, V dest) Returns the cost of the shortest path between nodes src and dest.
Path<V,E>	run(V src, V dest, int rq_cap) Returns the shortest path between nodes src and dest.

Methods inherited from class bcds.phison.ra.RoutingAlgBase

buildPathFromParentNodes, commitBackupPath, commitWorkingPath, dumpState, getBackupPath, getCost, getEnviron, getEnvParams, getName, getTED, getWorkingPath, offersProtection, setBackupPath, setRequest, setup, setWorkingPath, topologyHasChanged, uncommitBackupPath, uncommitWorkingPath

Methods inherited from class java.lang.Object

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

Constructor Detail

FloydWarshall

public FloydWarshall(TED<V,E> ted)

Creates a new instance and saves the ted parameter for future use.

Method Detail

getCost

public double getCost(V src,
                      V dest)

Returns the cost of the shortest path between nodes src and dest. Returns +INF if run() has not been called yet, or if there is no path between the given nodes.

run

public Path<V,E> run(V src,
                     V dest,
                     int rq_cap)

Returns the shortest path between nodes src and dest. The path returned has at least rq_cap units of residual capacity available at the time of the first call to this method.

Note that it is during the first call that links with insufficient available capacity are virtually removed from the topology and paths for every possible node pairs are computed; subsequent calls merely return what was already computed. If no path can be found, this method returns null. Use getCost(V, V) to find the cost of the path returned.