graph
Class Dijkstra

java.lang.Object
  |
  +--graph.Dijkstra

public class Dijkstra

extends java.lang.Object

A class to find shortest paths from a single start point to any end point. The user interface is nicely set up so that it is efficient regardless of whether the user wants the distance to lots of end points, or just to a single end point near the start point.

Field Summary

container.Attribute	attrBestEdgeIn Backpointer attribute.
container.Attribute	attrDist Distance attribute.
protected container.Attribute	attrEntry Entry attribute.
protected graph.Digraph	g The graph we are searching.
protected pqueue.AdaptablePriorityQueue	pq A priority queue of vertices that still have to be relaxed, keyed by their attrDist.
protected graph.Vertex	vStart The start vertex.
protected graph.Weighter	weighter An object that can compute the weight function on edges.

Constructor Summary

Dijkstra(graph.Digraph g, graph.Weighter weighter, java.lang.Object keyStart)
Convenience version of the constructor where the graph is keyed and the start vertex is specified by a key.

Dijkstra(graph.Digraph g, graph.Weighter weighter, graph.Vertex vStart)
Constructor that sets up a shortest-path problem.

Method Summary

protected void	clearAttributes(graph.Vertex v) Clears this instance's attributes from v and all the vertices that can be reached from it by directed paths from v.
protected void	computePathTo(graph.Vertex vEnd) Run Dijkstra's algorithm until we know the shortest path from vertex vStart to vertex vEnd, or have explored the whole graph without finding such a path.
void	finalize() The finalizer for this Dijkstra instance.
private double	getDist(graph.Vertex v) Value of v's attrDist attribute, as a double.
graph.Path	getPathTo(java.lang.Object keyEnd) Convenience version of getPathTo() where the end vertex is specified by a key.
graph.Path	getPathTo(graph.Vertex vEnd) Run Dijkstra's algorithm until we know the shortest path from vertex vStart to vertex vEnd.
static void	main(java.lang.String[] args)
protected graph.Path	pathTo(graph.Vertex v) Get the current best path from vStart to v, according to the backpointers.
private void	recordNewPathTo(graph.Vertex v, double d, graph.DirectedEdge e) We'll call this method when we find a new, shorter path to v.
private graph.Vertex	removeMinVertex() Remove and return the Vertex at the front of the priority queue.

Methods inherited from class java.lang.Object

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

Field Detail

g

protected graph.Digraph g

The graph we are searching.

weighter

protected graph.Weighter weighter

An object that can compute the weight function on edges.

vStart

protected graph.Vertex vStart

The start vertex.

pq

protected pqueue.AdaptablePriorityQueue pq

A priority queue of vertices that still have to be relaxed, keyed by their attrDist. Smallest attrDist is at the front of the queue. A vertex's attrDist attribute may change during the course of the algorithm (which is why we need an AdaptablePriorityQueue), but it is guaranteed to be correct by the time the vertex reaches the front of the queue.

attrDist

public container.Attribute attrDist

Distance attribute. A vertex's attrDist is the smallest known distance from vStart. If a vertex does not have this attribute yet, it has not yet been discovered, and its attrDist should be considered to be infinite.

This attribute is public, enabling the user to find its value at any vertex.

attrBestEdgeIn

public container.Attribute attrBestEdgeIn

Backpointer attribute. A vertex's attrBestEdgeIn is the last edge leading to the vertex on a shortest-known path from vStart. If a vertex does not have this attribute, no path to it from vStart has been discovered yet. vStart has an attrBestEdgeIn of null.

This attribute is public, enabling the user to find its value at any vertex.

attrEntry

protected container.Attribute attrEntry

Entry attribute. A vertex's attrEntry is its entry on the adaptable priority queue. Knowing this lets us change the vertex's priority. If a vertex does not have this attribute, it is not currently on the priority queue -- either it has not yet been inserted, or it has already been removed.

Constructor Detail

Dijkstra

public Dijkstra(graph.Digraph g,
                graph.Weighter weighter,
                graph.Vertex vStart)

Constructor that sets up a shortest-path problem. Dijkstra's algorithm is not actually run yet. But we are ready to find the shortest paths in graph g from vertex vStart, where edges are weighted by weighter.

Dijkstra

public Dijkstra(graph.Digraph g,
                graph.Weighter weighter,
                java.lang.Object keyStart)

Convenience version of the constructor where the graph is keyed and the start vertex is specified by a key.

Throws:

java.lang.ClassCastException - if the graph is not an instance of KeyedDigraph.

NoSuchVertexException - if there is no vertex keyed by keyStart.

Method Detail

getPathTo

public graph.Path getPathTo(graph.Vertex vEnd)
                     throws NegativeWeightException

Run Dijkstra's algorithm until we know the shortest path from vertex vStart to vertex vEnd. Then stop and return that path. Or return null if there is no directed path from vStart to vEnd.

The user may call us again later with another vertex vEnd, in which case we will pick up where we left off and continue running Dijkstra's algorithm, if necessary, until we know the shortest path to THAT vertex!

To find the length of the path, the user can look at v.get(d.attrDist), where d is this Dijkstra instance. Alternatively, the user can just sum the weights of the returned path's edges.

Throws:

NegativeWeightException - if negative edge weights are discovered in the graph.

getPathTo

public graph.Path getPathTo(java.lang.Object keyEnd)
                     throws NegativeWeightException

Convenience version of getPathTo() where the end vertex is specified by a key.

Throws:

java.lang.ClassCastException - if the graph is not an instance of KeyedDigraph.

NoSuchVertexException - if there is no vertex keyed by keyEnd.

NegativeWeightException - if negative edge weights are discovered in the graph.

computePathTo

protected void computePathTo(graph.Vertex vEnd)
                      throws NegativeWeightException

Run Dijkstra's algorithm until we know the shortest path from vertex vStart to vertex vEnd, or have explored the whole graph without finding such a path.

pathTo() can then be used to find the shortest path to vEnd, or the shortest KNOWN path (so far) to another vertex.

Throws:

NegativeWeightException - if negative edge weights are discovered in the graph.

pathTo

protected graph.Path pathTo(graph.Vertex v)

Get the current best path from vStart to v, according to the backpointers. Returns null if there is no known path from vStart to v.

removeMinVertex

private graph.Vertex removeMinVertex()

Remove and return the Vertex at the front of the priority queue.

getDist

private double getDist(graph.Vertex v)

Value of v's attrDist attribute, as a double.

recordNewPathTo

private void recordNewPathTo(graph.Vertex v,
                             double d,
                             graph.DirectedEdge e)

We'll call this method when we find a new, shorter path to v. The total weight of the new path is d and its last edge is e.

In addition to recording the new path in v's attributes, we ensure that v is on the priority queue, so that the change in its attrDist will be propagated to its neighbors. This may mean inserting or reprioritizing v. Note: This method doesn't have to care whether v has previously been popped off the queue. However, it is interesting to remember that in Dijkstra's algorithm, a vertex's distance will never improve further once it has been popped, so it never goes back on on the priority queue. (This is also true for the A* algorithm if we use a "monotonic" heuristic function, which is usually the case and is the case in this assignment.)

finalize

public void finalize()

The finalizer for this Dijkstra instance. It clears the attributes that it may have placed on the vertices. Otherwise, the vertices of a graph can get cluttered with attributes from many runs of Dijkstra's algorithm. The Dijkstra objects may finish their work and get garbage-collected, but the attributes are still accessible from the graph, and Java doesn't know that it's okay to garbage-collect THEM. We have to tell it.

A finalizer is the opposite of a constructor. When and if a Dijkstra instance is eventually garbage-collected (long after we're done with it), Java will automatically call the special finalize() method if it exists. Since this particular finalize() method is public, the user is also welcome to call it sooner when done with the Dijkstra instance, instead of waiting for the garbage collector to show up. In C++, it is necessary to have destructors for most objects because there is no garbage collection in C++; memory must be released explicitly. But in Java, it is quite rare to need a finalizer.

Overrides:

finalize in class java.lang.Object

clearAttributes

protected void clearAttributes(graph.Vertex v)

Clears this instance's attributes from v and all the vertices that can be reached from it by directed paths from v. We do this by depth-first search from v.

main

public static void main(java.lang.String[] args)