/** Dijkstra's algorithm for the single-source shortest path problem
  * in an undirected graph whose edges have integer weights. Classes
  * extending ths abstract class must define the weight(e) method,
  * which extracts the weight of an edge. */
public abstract class Dijkstra {
  /** Execute Dijkstra's algorithm.  */
  public void execute(InspectableGraph g, Vertex source) {
    graph = g;
    dijkstraVisit(source);
  }
  /** Attribute for vertex distances. */
  protected Object DIST = new Object();
  /** Set the distance of a vertex. */
  protected void setDist(Vertex v, int d) {
    v.set(DIST, new Integer(d));
  }
  /** Get the distance of a vertex from the source vertex. This method
    * returns the length of a shortest path from the source to u after
    * method execute has been called.  */
  public int getDist(Vertex u) {
    return ((Integer) u.get(DIST)).intValue();
  }
  /** This abstract method must be defined by subclasses.
    * @return weight of edge e. */
  protected abstract int weight(Edge e); 
  /** Infinity value. */
  public static final int INFINITE = Integer.MAX_VALUE;
  /** Input graph. */
  protected InspectableGraph graph;
  /** Auxiliary priority queue. */
  protected PriorityQueue Q;