/* Dijkstra's algorithm for the single-source shortest path problem
 * in an undirected graph whose edges have integer weights. 
 */
public class Dijkstra {
  /** Infinity value. */
  public static final int INFINITE = Integer.MAX_VALUE;
  /** Input graph. */
  protected Graph graph;
  /** Decoration key for edge weights */
  protected Object WEIGHT;
  /** Auxiliary priority queue. */
  protected AdaptablePriorityQueue Q;
  /** Executes Dijkstra's algorithm.
    * @param g Input graph
    * @param s Source vertex
    * @param w Weight decoration object
    */
  public void execute(Graph g, Vertex s, Object w) {
    graph = g;
    WEIGHT = w;
    Q = new HeapAdaptablePriorityQueue(new DefaultComparator());
    dijkstraVisit(s);
  }
  /** Get the distance of a vertex from the source vertex.
   * @param u Start vertex for the shortest path tree
   */
  public int getDist(Vertex u) {
    return ((Integer) u.get(DIST)).intValue();
  }