Package net.automatalib.util.graph.sssp
Class DijkstraSSSP<N,E>
- java.lang.Object
-
- net.automatalib.util.graph.sssp.DijkstraSSSP<N,E>
-
- Type Parameters:
N
- node classE
- edge class
- All Implemented Interfaces:
SSSPResult<N,E>
public class DijkstraSSSP<N,E> extends Object implements SSSPResult<N,E>
Implementation of Dijkstras algorithm for the single-source shortest path problem.
-
-
Constructor Summary
Constructors Constructor Description DijkstraSSSP(Graph<N,E> graph, N init, EdgeWeights<E> edgeWeights)
Constructor.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method 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.@Nullable List<E>
getShortestPath(N target)
Retrieves the shortest path from the initial node to the given one (as a sequence of edges), ornull
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.@Nullable E
getShortestPathEdge(N target)
Retrieves the incoming edge via which the given node is reached on the shortest path.
-
-
-
Method Detail
-
findSSSP
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 searchinit
- the initial (source) nodeedgeWeights
- 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 interfaceSSSPResult<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 interfaceSSSPResult<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 @Nullable 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), ornull
if there exists no such path.Note that implementations might construct these paths on-the-fly.
- Specified by:
getShortestPath
in interfaceSSSPResult<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 @Nullable 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 interfaceSSSPResult<N,E>
- Parameters:
target
- the target node- Returns:
- the reaching edge on the shortest path, or
null
.
-
-