/************************* Dijkstra.java **************************************/

import java.util.*;

/** implementiert den single source shortest path Algorithmus nach Dijkstra   */
/*                                                                            */
/*  Es sind nur nichtnegative Kantenkosten zugelassen                         */
/*                                                                            */
/*  Verwendet wird eine Priority-Queue der Knoten, gewichtet mit den Kosten   */
/*  des vorlaeufig kuerzesten Weges vom Startknoten bis zu diesem Knoten      */

public class Dijkstra {

  public static void dijkstra ( Graph g, Vertex start) {

    PriorityQueue<Vertex> p =        // Priority-Queue zum Verwalten der Laenge
        new PriorityQueue<Vertex>(); // des kuerzesten Weges bis zum Knoten

    for (Vertex v : g.vertices()){   // fuer jeden Knoten
      v.dist = Double.MAX_VALUE;     // Entfernung ist unendlich
      v.seen = false;                // Knoten noch nicht gesehen 
      v.prev = null;                 // Vorgaenger noch nicht ermittelt
    }

    start.dist = 0;                  // endgueltige Kosten zum Startknoten
    p.add(start);                    // erster Eintrag in PriorityQueue

    while (!p.isEmpty()){            // solange noch Eintraege in Priority-Queue

      Vertex v = p.poll();           // billigster Eintrag in PriorityQueue
      if (v.seen) continue;          // falls schon bearbeitet: ignorieren
      v.seen = true;                 // als bearbeitet markieren
    
      for (Edge e : v.edges){        // fuer jede Nachbarkante e von v tue
        Vertex w = e.dest;           // besorge Zielknoten w
        double c = e.cost;           // besorge Kosten c zum Zielknoten w
        if (c<0) throw new           // falls Kantenkosten negativ
        RuntimeException("Negativ"); // melde Fehler
        if (w.dist > v.dist + c) {   // falls Verkuerzung moeglich
          w.dist = v.dist + c;       // berechne Verkuerzung
          w.prev = v;                // notiere verursachenden Vorgaenger
          p.add(w);                  // neuer Eintrag in PriorityQueue
        }
      }
    }
  }
}