public class Dijkstra {

   // Dijkstra's algorithm to find shortest path from s to all other nodes
   public static int [] dijkstra (WeightedGraph G, int s) {
      final int [] dist = new int [G.size()];  // shortest known distance from "s"
      final int [] pred = new int [G.size()];  // preceeding node in path
      final boolean [] visited = new boolean [G.size()]; // all false initially

      for (int i=0; i<dist.length; i++) {
	 dist[i] = Integer.MAX_VALUE;
      }
      dist[s] = 0;

      for (int i=0; i<dist.length; i++) {
	 final int next = minVertex (dist, visited);
	 visited[next] = true;

	 // The shortest path to next is dist[next] and via pred[next].

	 final int [] n = G.neighbors (next);
	 for (int j=0; j<n.length; j++) {
	    final int v = n[j];
	    final int d = dist[next] + G.getWeight(next,v);
	    if (dist[v] > d) {
	       dist[v] = d;
	       pred[v] = next;
	    }
	 }
      }
      return pred;  // (ignore pred[s]==0!)
   }

   private static int minVertex (int [] dist, boolean [] v) {
      int x = Integer.MAX_VALUE;
      int y = -1;   // graph not connected, or no unvisited vertices
      for (int i=0; i<dist.length; i++) {
	 if (!v[i] && dist[i]<x) {y=i; x=dist[i];}
      }
      return y;
   }

   public static void printPath (WeightedGraph G, int [] pred, int s, int e) {
      final java.util.ArrayList path = new java.util.ArrayList();
      int x = e;
      while (x!=s) {
	 path.add (0, G.getLabel(x));
	 x = pred[x];
      }
      path.add (0, G.getLabel(s));
      System.out.println (path);
   }

}