net.automatalib.util.graphs.sssp

Class DijkstraSSSP<N,E>

java.lang.Object

net.automatalib.util.graphs.sssp.DijkstraSSSP<N,E>

Type Parameters:

N - node class

E - edge class

All Implemented Interfaces:

SSSPResult<N,E>

@ParametersAreNonnullByDefault
public class DijkstraSSSP<N,E>
extends Object
implements SSSPResult<N,E>

Implementation of Dijkstras algorithm for the single-source shortest path problem.

Author:

Malte Isberner

Constructor Summary

Constructors

Constructor and Description
DijkstraSSSP(Graph<N,E> graph, N init, EdgeWeights<E> edgeWeights) Constructor.

Method Summary

Modifier and Type	Method and Description
void	findSSSP() Start the search.
static <N,E> SSSPResult<N,E>	findSSSP(Graph<N,E> graph, N init, EdgeWeights<E> edgeWeights) Search for the shortest paths from a single source node in a graph.
N	getInitialNode() Retrieves the node the source was started from.
List<E>	getShortestPath(N target) Retrieves the shortest path from the initial node to the given one (as a sequence of edges), or null if there exists no such path.
float	getShortestPathDistance(N target) Retrieves the length of the shortest path from the initial node to the given one.
E	getShortestPathEdge(N target) Retrieves the incoming edge via which the given node is reached on the shortest path.

Methods inherited from class java.lang.Object

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

Constructor Detail

DijkstraSSSP

public DijkstraSSSP(Graph<N,E> graph,
                    N init,
                    EdgeWeights<E> edgeWeights)

Constructor.

Parameters:

graph - the graph in which to search for shortest paths

init - the initial node

edgeWeights - the edge weights

Method Detail

findSSSP

@Nonnull
public static <N,E> SSSPResult<N,E> findSSSP(Graph<N,E> graph,
                                                      N init,
                                                      EdgeWeights<E> edgeWeights)

Search for the shortest paths from a single source node in a graph.

Parameters:

graph - the graph in which to perform the search

init - the initial (source) node

edgeWeights - the edge weights

Returns:

the single-source shortest path results

findSSSP

public void findSSSP()

Start the search. This method may only be invoked once.

getInitialNode

public N getInitialNode()

Description copied from interface: SSSPResult

Retrieves the node the source was started from.

Specified by:

getInitialNode in interface SSSPResult<N,E>

Returns:

the source node

getShortestPathDistance

public float getShortestPathDistance(N target)

Description copied from interface: SSSPResult

Retrieves the length of the shortest path from the initial node to the given one.

Specified by:

getShortestPathDistance in interface SSSPResult<N,E>

Parameters:

target - the target node

Returns:

the length of the shortest path from the initial node to the given target node, or Graphs.INVALID_DISTANCE if there exists no such path.

getShortestPath

public List<E> getShortestPath(N target)

Description copied from interface: SSSPResult

Retrieves the shortest path from the initial node to the given one (as a sequence of edges), or null if there exists no such path.

Note that implementations might construct these paths on-the-fly.

Specified by:

getShortestPath in interface SSSPResult<N,E>

Parameters:

target - the target node

Returns:

the path from the initial node to the given target node, or null if there exists no such path.

getShortestPathEdge

public E getShortestPathEdge(N target)

Description copied from interface: SSSPResult

Retrieves the incoming edge via which the given node is reached on the shortest path. If the node is not reachable or it is the initial node, null is returned.

Specified by:

getShortestPathEdge in interface SSSPResult<N,E>

Parameters:

target - the target node

Returns:

the reaching edge on the shortest path, or null.