// This code is from "Algorithms in Java, Third Edition,"
// by Robert Sedgewick, Addison-Wesley, 2003.

// Program 21.1, Dijkstra's algorithm (priority-first search)

class GraphSPT
{
  public static final double maxWT=9999999.9;

  private double[] wt;
  private Edge[] spt;

  GraphSPT(Graph G, int s)  
  {
    int V = G.V();
    wt = new double[V];
    spt = new Edge[V]; 
    for (int v = 0; v < V; v++)
      wt[v] = maxWT; 
    doublePQi pQ = new doublePQi(V, wt);
    for (int v = 0; v < V; v++)
      pQ.insert(v);
    wt[s] = 0.0;
    pQ.lower(s);  
    while (!pQ.empty()) 
    {
      int v = pQ.getmin(); // wt[v] = 0.0;
      if (v != s && spt[v] == null)
        return; 
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
      {
        int w = e.other(v); 
        double P = wt[v] + e.wt();
        if (P < wt[w]) 
        {
          wt[w] = P;
          pQ.lower(w);
          spt[w] = e; 
        }
      }
    }
  }

  Edge pathR(int v) { return spt[v]; } // Predecessor on shortest path
  double dist(int v) { return wt[v]; } // Distance from source (s)
}