edu.uci.ics.jung.algorithms.shortestpath
Class DijkstraShortestPath

java.lang.Object
  edu.uci.ics.jung.algorithms.shortestpath.ShortestPath
      edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath

All Implemented Interfaces:

Distance

public class DijkstraShortestPath

extends ShortestPath

implements Distance

Calculates distances in a specified graph, using Dijkstra's single-source-shortest-path algorithm. All edge weights in the graph must be nonnegative; if any edge with negative weight is found in the course of calculating distances, an IllegalArgumentException will be thrown. (Note: this exception will only be thrown when such an edge would be used to update a given tentative distance; the algorithm does not check for negative-weight edges "up front".)

Distances and partial results are optionally cached (by this instance) for later reference. Thus, if the 10 closest vertices to a specified source vertex are known, calculating the 20 closest vertices does not require starting Dijkstra's algorithm over from scratch.

Distances are stored as double-precision values. If a vertex is not reachable from the specified source vertex, no distance is stored. This is new behavior with version 1.4; the previous behavior was to store a value of Double.POSITIVE_INFINITY. This change gives the algorithm an approximate complexity of O(kD log k), where k is either the number of requested targets or the number of reachable vertices (whichever is smaller), and D is the average degree of a vertex.

The elements in the maps returned by getDistanceMap and getIncomingEdgeMap are ordered (that is, returned by the iterator) by nondecreasing distance from source.

Users are cautioned that distances calculated should be assumed to be invalidated by changes to the graph, and should invoke reset() when appropriate so that the distances can be recalculated.

Author:

Joshua O'Madadhain

Constructor Summary

DijkstraShortestPath(Graph g)

DijkstraShortestPath(Graph g, NumberEdgeValue nev)

DijkstraShortestPath(Graph g, NumberEdgeValue nev, boolean cached)
Creates an instance of DijkstraShortestPath for the specified graph and the specified method of extracting weights from edges.

Method Summary

void	enableCaching(boolean enable) Specifies whether or not this instance of DijkstraShortestPath should cache its results (final and partial) for future reference;
java.lang.Number	getDistance(Vertex source, Vertex target) Returns the length of a shortest path from the source to the target vertex, or null if the target is not reachable from the source.
java.util.Map	getDistanceMap(Vertex source) Returns a LinkedHashMap which maps each vertex in the graph (including the source vertex) to its distance from the source vertex.
java.util.LinkedHashMap	getDistanceMap(Vertex source, int numDests) Returns a LinkedHashMap which maps each of the closest numDist vertices to the source vertex in the graph (including the source vertex) to its distance from the source vertex.
Edge	getIncomingEdge(Vertex source, Vertex target) Returns the last edge on a shortest path from source to target, or null if target is not reachable from source.
java.util.Map	getIncomingEdgeMap(Vertex source) Returns a LinkedHashMap which maps each vertex in the graph (including the source vertex) to the last edge on the shortest path from the source vertex.
java.util.LinkedHashMap	getIncomingEdgeMap(Vertex source, int numDests) Returns a LinkedHashMap which maps each of the closest numDist vertices to the source vertex in the graph (including the source vertex) to the incoming edge along the path from that vertex.
java.util.List	getPath(Vertex source, Vertex target) Returns a List of the edges on the shortest path from source to target, in order of their occurrence on this path.
void	reset() Clears all stored distances for this instance.
void	reset(Vertex source) Clears all stored distances for the specified source vertex source.

Methods inherited from class java.lang.Object

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

Constructor Detail

DijkstraShortestPath

public DijkstraShortestPath(Graph g,
                            NumberEdgeValue nev,
                            boolean cached)

Creates an instance of DijkstraShortestPath for the specified graph and the specified method of extracting weights from edges.

Parameters:

g - the graph on which distances will be calculated

DijkstraShortestPath

public DijkstraShortestPath(Graph g,
                            NumberEdgeValue nev)

DijkstraShortestPath

public DijkstraShortestPath(Graph g)

Method Detail

getDistance

public java.lang.Number getDistance(Vertex source,
                                    Vertex target)

Returns the length of a shortest path from the source to the target vertex, or null if the target is not reachable from the source. If either vertex is not in the graph for which this instance was created, throws IllegalArgumentException.

Specified by:

getDistance in interface Distance

See Also:

getDistanceMap(Vertex), getDistanceMap(Vertex,int)

getIncomingEdge

public Edge getIncomingEdge(Vertex source,
                            Vertex target)

Returns the last edge on a shortest path from source to target, or null if target is not reachable from source.

If either vertex is not in the graph for which this instance was created, throws IllegalArgumentException.

getDistanceMap

public java.util.Map getDistanceMap(Vertex source)

Returns a LinkedHashMap which maps each vertex in the graph (including the source vertex) to its distance from the source vertex. The map's iterator will return the elements in order of increasing distance from source.

The size of the map returned will be the number of vertices reachable from source.

Specified by:

getDistanceMap in interface Distance

Parameters:

source - the vertex from which distances are measured

See Also:

getDistanceMap(Vertex,int), getDistance(Vertex,Vertex)

getIncomingEdgeMap

public java.util.Map getIncomingEdgeMap(Vertex source)

Returns a LinkedHashMap which maps each vertex in the graph (including the source vertex) to the last edge on the shortest path from the source vertex. The map's iterator will return the elements in order of increasing distance from source.

Specified by:

getIncomingEdgeMap in class ShortestPath

Parameters:

source - the vertex from which distances are measured

See Also:

getDistanceMap(Vertex,int), getDistance(Vertex,Vertex)

getPath

public java.util.List getPath(Vertex source,
                              Vertex target)

Returns a List of the edges on the shortest path from source to target, in order of their occurrence on this path. If either vertex is not in the graph for which this instance was created, throws IllegalArgumentException.

Overrides:

getPath in class ShortestPath

getDistanceMap

public java.util.LinkedHashMap getDistanceMap(Vertex source,
                                              int numDests)

Returns a LinkedHashMap which maps each of the closest numDist vertices to the source vertex in the graph (including the source vertex) to its distance from the source vertex. Throws an IllegalArgumentException if source is not in this instance's graph, or if numDests is either less than 1 or greater than the number of vertices in the graph.

The size of the map returned will be the smaller of numDests and the number of vertices reachable from source.

Parameters:

source - the vertex from which distances are measured

numDests - the number of vertices for which to measure distances

See Also:

getDistanceMap(Vertex), getDistance(Vertex,Vertex)

getIncomingEdgeMap

public java.util.LinkedHashMap getIncomingEdgeMap(Vertex source,
                                                  int numDests)

Returns a LinkedHashMap which maps each of the closest numDist vertices to the source vertex in the graph (including the source vertex) to the incoming edge along the path from that vertex. Throws an IllegalArgumentException if source is not in this instance's graph, or if numDests is either less than 1 or greater than the number of vertices in the graph.

Parameters:

source - the vertex from which distances are measured

numDests - the number of vertics for which to measure distances

Returns:

See Also:

getIncomingEdgeMap(Vertex), getPath(Vertex,Vertex)

reset

public void reset()

Clears all stored distances for this instance. Should be called whenever the graph is modified (edge weights changed or edges added/removed). If the user knows that some currently calculated distances are unaffected by a change, reset(Vertex) may be appropriate instead.

See Also:

reset(Vertex)

enableCaching

public void enableCaching(boolean enable)

Specifies whether or not this instance of DijkstraShortestPath should cache its results (final and partial) for future reference;

Parameters:

enable - true if the results are to be cached, and false otherwise

reset

public void reset(Vertex source)

Clears all stored distances for the specified source vertex source. Should be called whenever the stored distances from this vertex are invalidated by changes to the graph.

See Also:

reset()