Package com.gengoai.graph.algorithms

Class DijkstraShortestPath<V>

java.lang.Object

com.gengoai.graph.algorithms.DijkstraShortestPath<V>

Type Parameters:

V - the Vertex type parameter

All Implemented Interfaces:

GraphSearch<V>, ShortestPath<V>, SingleSourceShortestPath<V>

public class DijkstraShortestPath<V>
extends Object
implements SingleSourceShortestPath<V>, ShortestPath<V>, GraphSearch<V>

Implementation of Dijkstra's algorithm for finding the shortest paths between vertices in a graph.

Author:

David B. Bracewell

Constructor Summary

Constructors

Constructor	Description
DijkstraShortestPath(Graph<V> graph)	Instantiates a new Dijkstra shortest path.
DijkstraShortestPath(Graph<V> graph, boolean treatUndirected)	Instantiates a new Dijkstra shortest path.

Method Summary

Modifier and Type	Method	Description
double	distance(V source, V target)	The distance between the two vertices.
List<Edge<V>>	path(V source, V target)	The shortest path (list of edges) from the source to target vertex.
void	reset()	Resets cached data
List<Edge<V>>	search(V startingPoint, V endingPoint)	Searches for a path from the given starting point to the given ending point
Counter<V>	singleSourceShortestDistance(V source)	The distance between the source vertex and all other vertices in the graph
ListMultimap<V,Edge<V>>	singleSourceShortestPath(V source)	The path (list of edges) between the source vertex and all other vertices in the graph

Methods inherited from class java.lang.Object

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

Constructor Detail

DijkstraShortestPath

public DijkstraShortestPath(Graph<V> graph)

Instantiates a new Dijkstra shortest path.

Parameters:

graph - the graph to calculate paths over

DijkstraShortestPath

public DijkstraShortestPath(Graph<V> graph,
                            boolean treatUndirected)

Instantiates a new Dijkstra shortest path.

Parameters:

graph - the graph to calculate paths over

treatUndirected - True treat the graph as undirected (even if it is directed).

Method Detail

search

public List<Edge<V>> search(V startingPoint,
                            V endingPoint)

Description copied from interface: GraphSearch

Searches for a path from the given starting point to the given ending point

Specified by:

search in interface GraphSearch<V>

Parameters:

startingPoint - the starting point

endingPoint - the ending point

Returns:

the path as a list of edges (empty list if no path exists)

singleSourceShortestDistance

public Counter<V> singleSourceShortestDistance(V source)

Description copied from interface: SingleSourceShortestPath

The distance between the source vertex and all other vertices in the graph

Specified by:

singleSourceShortestDistance in interface SingleSourceShortestPath<V>

Parameters:

source - the source vertex

Returns:

Counter of target vertices and their distances.

singleSourceShortestPath

public ListMultimap<V,Edge<V>> singleSourceShortestPath(V source)

Description copied from interface: SingleSourceShortestPath

The path (list of edges) between the source vertex and all other vertices in the graph

Specified by:

singleSourceShortestPath in interface SingleSourceShortestPath<V>

Parameters:

source - the source vertex

Returns:

ListMultimap of target vertices and paths from source to target.

distance

public double distance(V source,
                       V target)

Description copied from interface: ShortestPath

The distance between the two vertices.

Specified by:

distance in interface ShortestPath<V>

Parameters:

source - the starting (source) vertex

target - the target vertex

Returns:

the distance from source to target (Positive Infinity if no path exists).

path

public List<Edge<V>> path(V source,
                          V target)

Description copied from interface: ShortestPath

The shortest path (list of edges) from the source to target vertex.

Specified by:

path in interface ShortestPath<V>

Parameters:

source - the starting (source) vertex

target - the target vertex

Returns:

List of edges from source to target representing the shortest path.

reset

public void reset()

Resets cached data