* An implementation of Dijkstra's algorithm for the single source shortest
* path problem in graphs with non-negative integer weights on the edges.
* It is implemented in terms of a VertexIterator returning
* the vertices in non-decreasing order of their distance from the source,
* and provides InspectableAttributes to access distance
* and predecessor information for each vertex.
*
* The implementation is flexible in that weight parameters need not
* be stored in a prescribed way (decorations, hashtables) and can even
* be non-materialized. Moreover, initialization and execution control
* remain with the calling program (if desired). These features can be
* be used to define multiple sources or upper bounds on distances,
* and to terminate execution early (or resume it). However, Java's lack
* of support for generic programming restricts the edge weight type to
* ints.
*
* Note that reset() causes a runtime exception if
* used prior to specification of a source vertex through
* either setSource(Vertex) or distances(Vertex).
*
edgeWeights is assumed to be Integer.
**/
public IntegerDijkstra(InspectableGraph G, InspectableAttribute edgeWeights) {
this(G, edgeWeights,
new ArrayHeap(new IntegerComparator()),
new HashtableAttribute(new Hashtable())
);
}
/**
* Flexible variant allowing a pre-initialized priority queue.
* Can be used to specify multiple sources and/or bounds on the distances.
* as well as the set of vertices that are valid on a path.
* Vertices not in the queue will not be considered for a shortest path.
*
* @param pq a priority queue containing all vertices that are
* allowed to be used in a shortest path, where distances should be
* initialized to 0 (for sources), some a-priori maximum,
* or this.INFINITY (default, no maximum).
* @param initialDistances must provide read/write access to vertex distances
* initialized in the queue
**/
public IntegerDijkstra(InspectableGraph G, InspectableAttribute edgeWeights,
PriorityQueue pq, Attribute initialDistances
) {
G_ = G;
weights_ = edgeWeights;
Q_ = pq;
distances_ = initialDistances;
}
// ---------------------------------------- Implement VertexIterator interface
// ----------------- test for further elements
/**
* Tests whether more vertices can be reached from the source(s).
**/
public boolean hasNext()
{ return !Q_.isEmpty(); } // queue contains all unsearched vertices
// ----------------- advance
/**
* Advances the iterator and returns a vertex of minimum distance
* among those not yet returned.
**/
public Object nextObject() { return nextVertex(); }
/**
* Advances the iterator and returns a vertex of minimum distance
* among those not yet returned.
**/
public Accessor nextAccessor() { return nextVertex(); }
/**
* Advances the iterator and returns a vertex of minimum distance
* among those not yet returned.
**/
public Position nextPosition() { return nextVertex(); }
/**
* Advances the iterator and returns a vertex of minimum distance
* among those not yet returned.
**/
public Vertex nextVertex() {
if(!hasNext())
throw new NoSuchElementException("No more vertices to be reached.");
Vertex u = (Vertex) Q_.removeMin(); // get closest vertex
int d = ((Integer) distances_.get(u)).intValue();
if(d < INFINITY) // reachable from source => relax edges
for(EdgeIterator u_edges = G_.incidentEdges(u, EdgeDirection.OUT | EdgeDirection.UNDIR); u_edges.hasNext(); )
relax(u, d, u_edges.nextEdge());
return (currentVertex_ = u);
}
// -------------- current element
/**
* Resets the algorithm to start over from the most recently specified source.
*
* @exception InvalidMethodCallException
* if no source has been specified using
* setSource(Vertex) or distances(Vertex)
**/
public void reset() {
if(source_ == null)
throw new InvalidMethodCallException("Cannot reset if source has not been specified using setSource(Vertex) or distances(Vertex).");
setSource(source_);
}
/**
* Returns the vertex most recently reached.
*
* @exception NoSuchVertexException
* if the iterator has not yet been advanced for the first time
**/
public Object object() { return vertex(); }
/**
* Returns the vertex most recently reached.
*
* @exception NoSuchVertexException
* if the iterator has not yet been advanced for the first time
**/
public Accessor accessor() { return vertex(); }
/**
* Returns the vertex most recently reached.
*
* @exception NoSuchVertexException
* if the iterator has not yet been advanced for the first time
**/
public Position position() { return vertex(); }
/**
* Returns the vertex most recently reached.
*
* @exception NoSuchVertexException
* if the iterator has not yet been advanced for the first time
**/
public Vertex vertex() {
if(currentVertex_ == null)
throw new NoSuchVertexException("Iterator has not yet been advanced for the first time.");
return currentVertex_;
}
// -------------------- convenience
/**
* Shortcut to the element of the vertex that was most recently returned.
*
* @exception NoSuchElementException
* if the iterator has not yet been advanced for the first time
**/
public Object element() {
if(currentVertex_ == null)
throw new NoSuchElementException("Iterator has not yet been advanced for the first time.");
return currentVertex_.element();
}
// ---------------------------------------- Own public methods
/**
* Initializes the algorithm to determine lengths of shortest paths from
* the specified source to all other vertices in the graph.
**/
public void setSource(Vertex source)
throws InvalidAccessorException, NoSuchVertexException
{ if(G_.contains(source)) {
while(!Q_.isEmpty()) Q_.removeMin();
locators_ = new Hashtable();
for(VertexIterator vertices = G_.vertices(); vertices.hasNext(); ) {
Vertex u = (Vertex) vertices.nextVertex();
Integer u_dist;
if (u == source)
u_dist = new Integer(0);
else {
u_dist = new Integer(INFINITY);
distances_.set(u, u_dist);
locators_.put(u, Q_.insert(u_dist, u));
}
}
source_ = source;
currentVertex_ = null;
} else
throw new NoSuchVertexException("Specified source not found in graph.");
}
/**
* External initialization (see corresponding constructor).
* Note that reset() causes a runtime exception,
* if this initialization is used.
**/
public void init(PriorityQueue pq, Attribute preDistances) {
Q_ = pq;
distances_ = preDistances;
source_ = null; // used to indicate that reset() must fail
currentVertex_ = null;
}
/**
* Relax an edge, i.e. set the current distance label of
* the vertex opposing u to the minimum of
* its previous value, and the sum of the distance of u
* end the weight of e.
*
* @return -1 if e implies a detour
* 0 if a shortest path using e has the same length
* 1 if e implies a shortcut
**/
public int relax(Vertex u, Edge e) {
return relax(u, ((Integer)distances_.get(u)).intValue(), e);
}
private int relax(Vertex u, int d, Edge e) {
Vertex v = G_.opposite(u, e);
int z = ((Integer) distances_.get(v)).intValue();
int w = ((Integer) weights_.get(e)).intValue();
if(d+w < z) {
if(locators_.containsKey(v)) { // care only about vertices initially in the queue
// update pre-distance label
Integer newDist = new Integer(d+w);
distances_.set(v, newDist);
Q_.replaceKey((Locator)locators_.get(v), newDist);
}
return 1;
}
return (d+w > z) ? -1 : 0;
}
/**
* @return read/write accessor for current distance labels
**/
public Attribute currentDistances() { return distances_; }
/**
* Provides final distances labels by finishing the current computation
* (effectively performs rest of iteration).
*
* @return read accessor for distances after algorithm termination
**/
public InspectableAttribute distances() {
while(hasNext()) nextVertex();
return currentDistances();
}
/**
* Solve single source shortest path problem with source
* as the source.
*
* @return read accessor for vertex distances
**/
public InspectableAttribute distances(Vertex source) {
setSource(source);
return distances();
}
}