net.automatalib.util.graphs.apsp

Class FloydWarshallAPSP<N,E>

java.lang.Object

net.automatalib.util.graphs.apsp.FloydWarshallAPSP<N,E>

Type Parameters:

N - node class

E - edge class

All Implemented Interfaces:

APSPResult<N,E>

@ParametersAreNonnullByDefault
public class FloydWarshallAPSP<N,E>
extends Object
implements APSPResult<N,E>

Implementation of the Floyd-Warshall dynamic programming algorithm for the all pairs shortest paths problem.

Author:

Malte Isberner

Constructor Summary

Constructors

Constructor and Description
FloydWarshallAPSP(Graph<N,E> graph, EdgeWeights<E> ew)

Method Summary

Modifier and Type	Method and Description
void	findAPSP()
static <N,E> APSPResult<N,E>	findAPSP(Graph<N,E> graph, EdgeWeights<E> edgeWeights)
List<E>	getShortestPath(N src, N tgt) Retrieves the shortest path between the given nodes, or null if there exists no such path.
float	getShortestPathDistance(N src, N tgt) Retrieves the length of the shortest path between the given nodes.

Methods inherited from class java.lang.Object

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

Constructor Detail

FloydWarshallAPSP

public FloydWarshallAPSP(Graph<N,E> graph,
                         EdgeWeights<E> ew)

Method Detail

findAPSP

@Nonnull
public static <N,E> APSPResult<N,E> findAPSP(Graph<N,E> graph,
                                                      EdgeWeights<E> edgeWeights)

findAPSP

public void findAPSP()

getShortestPathDistance

public float getShortestPathDistance(N src,
                                     N tgt)

Description copied from interface: APSPResult

Retrieves the length of the shortest path between the given nodes.

Specified by:

getShortestPathDistance in interface APSPResult<N,E>

Parameters:

src - the source node

tgt - the target node

Returns:

the length of the shortest path from src to tgt, or Graphs.INVALID_DISTANCE if there exists no such path.

getShortestPath

public List<E> getShortestPath(N src,
                               N tgt)

Description copied from interface: APSPResult

Retrieves the shortest path between the given nodes, or null if there exists no such path.

Specified by:

getShortestPath in interface APSPResult<N,E>

Parameters:

src - the source node

tgt - the target node

Returns:

the shortest path from src to tgt, or null if there exists no such path.