Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

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

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

All Implemented Interfaces:
  Distance, ShortestPath

public class DijkstraShortestPath
extends DijkstraDistance
implements ShortestPath

Calculates distances and shortest paths using Dijkstra's single-source-shortest-path algorithm. This is a lightweight extension of `DijkstraDistance` that also stores path information, so that the shortest paths can be reconstructed.

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

Author:
  Joshua O'Madadhain
See Also:
  `DijkstraDistance`

Nested Class Summary
`protected class` | `DijkstraShortestPath.SourcePathData` For a given source vertex, holds the estimated and final distances, tentative and final assignments of incoming edges on the shortest path from the source vertex, and a priority queue (ordered by estimaed distance) of the vertices for which distances are unknown.

Nested classes inherited from class edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance
`DijkstraDistance.SourceData, DijkstraDistance.VertexComparator`

Field Summary

Fields inherited from class edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance
`cached, dev, g, max_distance, max_targets, nev, sourceMap`

Constructor Summary
`DijkstraShortestPath(ArchetypeGraph g)` Creates an instance of `DijkstraShortestPath` for the specified unweighted graph (that is, all weights 1) which caches results locally.
`DijkstraShortestPath(ArchetypeGraph g, boolean cached)` Creates an instance of `DijkstraShortestPath` for the specified unweighted graph (that is, all weights 1) which caches results locally.
`DijkstraShortestPath(ArchetypeGraph g, NumberEdgeValue nev)` Creates an instance of `DijkstraShortestPath` for the specified graph and the specified method of extracting weights from edges, which caches results locally.
`DijkstraShortestPath(ArchetypeGraph g, NumberEdgeValue nev, boolean cached)` Creates an instance of `DijkstraShortestPath` for the specified graph and the specified method of extracting weights from edges, which caches results locally if and only if `cached` is `true`.

Method Summary
`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`.
`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.
`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.
`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.
`protected DijkstraDistance.SourceData` | `getSourceData(ArchetypeVertex source)`

Methods inherited from class edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance
`enableCaching, getDistance, getDistanceMap, getDistanceMap, getDistanceMap, getIncidentEdges, reset, reset, setMaxDistance, setMaxTargets, singleSourceShortestPath`

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail

### DijkstraShortestPath

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

  Creates an instance of `DijkstraShortestPath` for the specified graph and the specified method of extracting weights from edges, which caches results locally if and only if `cached` is `true`.

Parameters:
  `g` - the graph on which distances will be calculated
  `nev` - the class responsible for returning weights for edges
  `cached` - specifies whether the results are to be cached

### DijkstraShortestPath

    public DijkstraShortestPath(ArchetypeGraph g,
                                NumberEdgeValue nev)

  Creates an instance of `DijkstraShortestPath` for the specified graph and the specified method of extracting weights from edges, which caches results locally.

Parameters:
  `g` - the graph on which distances will be calculated
  `nev` - the class responsible for returning weights for edges

### DijkstraShortestPath

    public DijkstraShortestPath(ArchetypeGraph g)

  Creates an instance of `DijkstraShortestPath` for the specified unweighted graph (that is, all weights 1) which caches results locally.

Parameters:
  `g` - the graph on which distances will be calculated

### DijkstraShortestPath

    public DijkstraShortestPath(ArchetypeGraph g,
                                boolean cached)

  Creates an instance of `DijkstraShortestPath` for the specified unweighted graph (that is, all weights 1) which caches results locally.

Parameters:
  `g` - the graph on which distances will be calculated
  `cached` - specifies whether the results are to be cached

Method Detail

### getSourceData

    protected DijkstraDistance.SourceData getSourceData(ArchetypeVertex source)

  Overrides:
    `getSourceData` in class `DijkstraDistance`

### 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`.

### getIncomingEdgeMap

    public 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 interface `ShortestPath`
  Parameters:
    `source` - the vertex from which distances are measured
  See Also:
    `DijkstraDistance#getDistanceMap(Vertex,int)`, `DijkstraDistance#getDistance(Vertex,Vertex)`

### getPath

    public 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`.

### getIncomingEdgeMap

    public 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
  See Also:
    `getIncomingEdgeMap(Vertex)`, `getPath(Vertex,Vertex)`

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD