// shortest path algorithmus nach dijkstra

class Dijkstra {

 static class VertexInfo {
  boolean known = false;
  double dist = Double.MAX_VALUE;
  Object source, via = null;
  String label = null;
  VertexInfo(Object source){this.source = source; label = source.toString();}
 }

 static TreeSet initVertices(Graph g, Object s, Map m) {
  Iterator it = g.getVertices().iterator();
  while (it.hasNext()) {
   Object x = it.next();
   m.put(x, new VertexInfo(x));
  }
  ((VertexInfo)m.get(s)).dist = 0;
  TreeSet set = new TreeSet(
   new Comparator(){
    public int compare(Object x1, Object x2){
     VertexInfo v1 = (VertexInfo)x1;
     VertexInfo v2 = (VertexInfo)x2;

     if(v1.dist < v2.dist) return -1;
     else if (v1.dist > v2.dist) return 1;
     else return v1.label.compareTo(v2.label);
    }
   }
  );
  set.addAll(m.values());
  return set;
 }

 static VertexInfo nearestUnknownVertex(TreeSet t) throws NoSuchElementException {
  Object n = t.first();
  t.remove(n);
  return (VertexInfo)n;
 }

 static void decrease(TreeSet t, VertexInfo w, double newDist) {

  if (t.remove(w)) {
   w.dist = newDist;
   t.add(w);
  }
 }

 static Graph constructPath(WeightedGraph g, Object target, Map m) {
  WeightedGraph path = new WeightedGraphImpl(new graph.rep.AdjListGraph(g.isDirected()));
  double totalWeight = 0.0;
  Object current = target;

  path.addVertex(current);
  while (((VertexInfo)m.get(current)).via != null) {
   Object via = ((VertexInfo)m.get(current)).via;
   path.addVertex(via);
   double legWeight = g.getEdgeWeight(via, current);
   path.addEdge(via, current, legWeight);
   totalWeight += legWeight;
   current =via;
  }
  System.out.println("The minimum distance from " +
        current +
        " to " +
        target +
        " is: " +
        totalWeight);
  return path;
 }

 static Graph getShortestPath(WeightedGraph g, Object from, Object to) {
  Map m = new HashMap();
  TreeSet t = initVertices(g, from, m);

  try {
   while(true) {
    VertexInfo v = nearestUnknownVertex(t);
    v.known = true;

    Iterator it = g.getAdjacentVertices(v.source).iterator();
    while(it.hasNext()) {
     VertexInfo w = (VertexInfo)m.get(it.next());
     if (!w.known) {
      double weight = g.getEdgeWeight(v.source, w.source);
      if (v.dist + weight < w.dist) {
       decrease(t, w, v.dist + weight);
       w.via = v.source;
      }
     }
    }
   }
  }
  catch (NoSuchElementException nsee) {
  }
  return constructPath(g, to, m);
 }
}