net.datastructures
Class Dijkstra<V,E>

java.lang.Object
  extended by net.datastructures.Dijkstra<V,E>

public class Dijkstra<V,E>
extends java.lang.Object

Dijkstra's algorithm for the single-source shortest path problem in an undirected graph whose edges have integer weights.

To execute the algorithm, use the execute method, and then make subsequent calls to the getDist method to obtain the shortest distance from the start to any given vertex.

Author:
Roberto Tamassia, Michael Goodrich, Eric Zamore

Field Summary
protected  java.lang.Object DIST
          Decoration key for vertex distances
protected  java.lang.Object ENTRY
          Decoration key for entries in the priority queue
protected  net.datastructures.Graph<V,E> graph
          Input graph.
protected static java.lang.Integer INFINITE
          Infinity value.
protected  net.datastructures.AdaptablePriorityQueue<java.lang.Integer,net.datastructures.Vertex<V>> Q
          Auxiliary priority queue.
protected  java.lang.Object WEIGHT
          Decoration key for edge weights
 
Constructor Summary
Dijkstra()
           
 
Method Summary
protected  void dijkstraVisit(net.datastructures.Vertex<V> v)
          The actual execution of Dijkstra's algorithm.
 void execute(net.datastructures.Graph<V,E> g, net.datastructures.Vertex<V> s, java.lang.Object w)
          Executes Dijkstra's algorithm.
 int getDist(net.datastructures.Vertex<V> u)
          Get the distance of a vertex from the source vertex.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

INFINITE

protected static final java.lang.Integer INFINITE
Infinity value.


graph

protected net.datastructures.Graph<V,E> graph
Input graph.


WEIGHT

protected java.lang.Object WEIGHT
Decoration key for edge weights


DIST

protected java.lang.Object DIST
Decoration key for vertex distances


ENTRY

protected java.lang.Object ENTRY
Decoration key for entries in the priority queue


Q

protected net.datastructures.AdaptablePriorityQueue<java.lang.Integer,net.datastructures.Vertex<V>> Q
Auxiliary priority queue.

Constructor Detail

Dijkstra

public Dijkstra()
Method Detail

execute

public void execute(net.datastructures.Graph<V,E> g,
                    net.datastructures.Vertex<V> s,
                    java.lang.Object w)
Executes Dijkstra's algorithm.

Parameters:
g - Input graph
s - Source vertex
w - Weight decoration object

getDist

public int getDist(net.datastructures.Vertex<V> u)
Get the distance of a vertex from the source vertex. //end#fragment execute This method returns the length of a shortest path from the source to u after execute has been called. //begin#fragment execute

Parameters:
u - Start vertex for the shortest path tree

dijkstraVisit

protected void dijkstraVisit(net.datastructures.Vertex<V> v)
The actual execution of Dijkstra's algorithm.

Parameters:
v - source vertex.