Package com.jgalgo.alg

Interface ShortestPathSingleSource.Result<V,E>

Type Parameters:

V - the vertices type

E - the edges type

All Known Subinterfaces:

ShortestPathSingleSource.IResult

Enclosing interface:

ShortestPathSingleSource

public static interface ShortestPathSingleSource.Result<V,E>

A result object for the ShortestPathSingleSource problem.

Author:

Barak Ugav

Method Summary

Modifier and Type	Method	Description
E	backtrackEdge(V target)	Get the last edge on the shortest path from the source to the given target.
double	distance(V target)	Get the distance to a target vertex.
Path<V,E>	getPath(V target)	Get shortest path to a target vertex.
Graph<V,E>	graph()	Get the graph on which the shortest paths were computed on.
default Graph<V,E>	shortestPathTree()	Get the shortest path tree.
default Graph<V,E>	shortestPathTree(boolean directed)	Get the shortest path tree, optionally directed or undirected.
V	source()	Get the source vertex from which all shortest paths were computed from.

Method Detail

distance

double distance(V target)

Get the distance to a target vertex.

Parameters:

target - a target vertex in the graph

Returns:

the sum of the shortest path edges from the source to the target, or Double.POSITIVE_INFINITY if no such path found

Throws:

NoSuchVertexException - if target is not a vertex in the graph

getPath

Path<V,E> getPath(V target)

Get shortest path to a target vertex.

Parameters:

target - a target vertex in the graph

Returns:

the shortest path from the source to the target or null if no such path found.

Throws:

NoSuchVertexException - if target is not a vertex in the graph

backtrackEdge

E backtrackEdge(V target)

Get the last edge on the shortest path from the source to the given target.

The backtrack edge is an in-edge of the given target vertex. The set of all backtrack edges of all vertices define the shortest path tree of the source, and each shortest path can be constructed from them.

Parameters:

target - a target vertex in the graph

Returns:

the backtrack edge, the last edge on the shortest path from the source to th given target, or null if there is no path to the target or the target is the source

shortestPathTree

default Graph<V,E> shortestPathTree()

Get the shortest path tree.

The shortest path tree is constructed from the vertices and edges used by any shortest path. It contains only the vertices reachable from the source, and for each vertex other than the source the graph will contains the edge that was used to reach it (see backtrackEdge(Object)). If there are \(k\) reachable vertices, the graph will contain \(k-1\) edges.

The returned graph will be directed if the original graph is directed. In such case, the tree is directed from the source to the other vertices. To control the directionality of the returned graph, use shortestPathTree(boolean).

Returns:

undirected shortest path tree

shortestPathTree

default Graph<V,E> shortestPathTree(boolean directed)

Get the shortest path tree, optionally directed or undirected.

The shortest path tree is constructed from the vertices and edges used by any shortest path. It contains only the vertices reachable from the source, and for each vertex other than the source the graph will contains the edge that was used to reach it (see backtrackEdge(Object)). If there are \(k\) reachable vertices, the graph will contain \(k-1\) edges.

Parameters:

directed - if true the returned tree will be directed. If the original graph was undirected and a directed tree is created, the edges in the tree will be directed from the source towards the other vertices

Returns:

un/directed shortest path tree

source

V source()

Get the source vertex from which all shortest paths were computed from.

Returns:

the source vertex

graph

Graph<V,E> graph()

Get the graph on which the shortest paths were computed on.

Returns:

the graph on which the shortest paths were computed on.