nz.ac.waikato.jdsl.graph.algo
Class IntegerDijkstraPathfinder
java.lang.Object
nz.ac.waikato.jdsl.graph.algo.IntegerDijkstraTemplate
nz.ac.waikato.jdsl.graph.algo.IntegerDijkstraPathfinder
public abstract class IntegerDijkstraPathfinder
- extends IntegerDijkstraTemplate
using Dijkstra's algorithm. You must extend this class and
implement the weight(Edge) method. As always, Dijkstra's algorithm
cannot handle negative-weight edges.
If necessary, you also have access to all the customization methods
of IntegerDijkstraTemplate, although using some of them without the
knowledge of this class could give incorrect results.
- Version:
- JDSL 2.1.1
- Author:
- Mark Handy, Luca Vismara
Methods inherited from class nz.ac.waikato.jdsl.graph.algo.IntegerDijkstraTemplate |
cleanup, destination, distance, doOneIteration, edgeRelaxed, execute, getEdgeToParent, getLocator, incidentEdges, init, initMap, isFinished, isReachable, newPQ, runUntil, setEdgeToParent, setLocator, shortestPathFound, vertexNotReachable, vertices, weight |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
IntegerDijkstraPathfinder
public IntegerDijkstraPathfinder()
shouldContinue
protected boolean shouldContinue()
- Description copied from class:
IntegerDijkstraTemplate
- Can be overridden in any application where the full shortest-path
tree is not needed and the algorithm should terminate early.
executeAll(.) checks the return from this method before each call
to doOneIteration(). The default implementation just returns
true
, so executeAll(.) continues until the full
shortest-path tree is built. Notice that if you are calling
doOneIteration() manually, this method is irrelevant; only
executeAll(.) calls this method.
- Overrides:
shouldContinue
in class IntegerDijkstraTemplate
- Returns:
- Whether to continue running the algorithm
pathExists
public boolean pathExists()
- Returns whether a path between the source and the destination exists
- Returns:
- whether there is a path from source to destination
reportPath
public EdgeIterator reportPath()
throws InvalidQueryException
- Returns:
- Iterator over the edges, in order, of a shortest path
from source to destination
- Throws:
InvalidQueryException
execute
public final void execute(InspectableGraph g,
Vertex source,
Vertex dest)
throws InvalidVertexException
- Parameters:
g
- the graph on which to execute the algorithmsource
- the source vertexdest
- the destination vertex
- Throws:
InvalidVertexException
- if source or dest are not
contained in g
Copyright © 2009 ModelJUnit Project. All Rights Reserved.