jdsl.graph.algo
Class IntegerDijkstraPathfinder

java.lang.Object
  jdsl.graph.algo.IntegerDijkstraTemplate
      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

Field Summary

Fields inherited from class jdsl.graph.algo.IntegerDijkstraTemplate

g_, pq_, source_

Constructor Summary

IntegerDijkstraPathfinder()

Method Summary

void	execute(InspectableGraph g, Vertex source, Vertex dest)
boolean	pathExists() Returns whether a path between the source and the destination exists
EdgeIterator	reportPath()
protected boolean	shouldContinue() Can be overridden in any application where the full shortest-path tree is not needed and the algorithm should terminate early.

Methods inherited from class 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

Constructor Detail

IntegerDijkstraPathfinder

public IntegerDijkstraPathfinder()

Method Detail

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 algorithm

source - the source vertex

dest - the destination vertex

Throws:

InvalidVertexException - if source or dest are not contained in g