Grundlegende Idee

Häufig steht man vor der Herausforderung den kürzesten Weg zwischen zwei Knoten in einem Graph zu finden. Dazu bietet sich der Dijkstra-Algorithmus, oder manchmal auch als Ameisenalgorithmus bekannt, an. Wenn es sich bei dem Graphen um einen ungewichteten handelt, bringt die Breitensuche zu einem bestimmten Knoten einem schon den kürzesten Weg. Dijkstra dagegen kann in einem gewichteten Graphen (mit nichtnegativen Gewichten) den kürzesten Weg bestimmen.

Für Dijkstra bekommt jeder Knoten zusätzlich zu seinem bisherigen Attributen noch ein Gewicht und eine Referenz auf den vorherigen Knoten dazu. Das Gewicht repräsentiert dabei die Summe der Gewichte der Kanten, welche den kürzesten Weg zu diesem Knoten vom Start aus bilden. Der vorherige Knoten ist dabei der Knoten, welcher auf der kürzesten Verbindung zum Startknoten vor diesem liegt.

Algorithmus

Der Dijkstra basiert auf der Funktionsweise, dass man die Kante mit der kürzesten Verbindung am bisher abgelaufenen Graphen betrachtet, und sich überlegt, ob diese Kante einen Knoten besser(also mit geringerer Kantensumme) mit dem Startknoten verbindet. Dabei kann man noch nicht "entdeckte" Knoten sehen, als hätten diese ein unendlich hohes Gewicht. Zuallererst müssen wir also die Knoten, welche durch vom Startknoten ausgehende Kanten erreichbar sind betrachten.

PriorityQueue pq
StartKnoten.WEIGHT = 0
StartKnoten.Prev = null
Add StartKnoten zu pq
SOLANGE pq nicht leer
    nimm den obersten Knoten K aus pq
    WENN K IST ZielKnoten
        ENDE
    WENN K.WEIGHT > BerechneGewicht(K)
        Für alle Nachbarn N von K
            WENN N.WEIGHT > K.WEIGHT + (Distanz zwischen N und K)
                N.WEIGHT = K.WEIGHT + (Distanz zwischen N und K)
                N.Prev = K
                Füge N zu pq hinzu

Implementierung

Daher können wir auch wieder eine Priority-Queue benutzen, um die Knoten mit dem geringsten Gewicht abzuspeichern. Da wir die tollen Java-Klassen des Landes NRW benutzen müssen, musste man bei der Implementierung gewisse merkwürdige "Hacks" anwenden, wie bei mir die Hashmap zum zuordnen von Gewicht/Vorgänger zu den Knoten.

private void dijkstra2(Graph g, Vertex start, Vertex end) {
    Map<Vertex, DijkstraData> infos = new HashMap<>();
    graph.setAllEdgeMarks(false);
    graph.setAllVertexMarks(false);
    start.setMark(true);
    infos.put(start, new DijkstraData(0, null));
    BinarySearchTree<VertexEntry> pq = new BinarySearchTree();
    pq.insert(new VertexEntry(start, 0));
    infos.put(start,new DijkstraData(0, null));
    while(true) {
      VertexEntry ve = getMinV(pq);
      pq.remove(ve);
      Vertex v = ve.v;
      if (v.equals(end)) break;
      List<Vertex> neighbours = g.getNeighbours(v);
      neighbours.toFirst();
      while (neighbours.hasAccess()) {
        Vertex n = neighbours.getContent();
        double new_weight = infos.get(v).weight + g.getEdge(v, n).getWeight();
        DijkstraData d = infos.get(n);
        if (d == null || d.weight > new_weight) {
          pq.insert(new VertexEntry(n, new_weight));
          infos.put(n, new DijkstraData(new_weight, v));
        }
        neighbours.next();
      }
    }
    graphA.zeichnen(retrace(g, infos, end));
    System.out.println("Das Gewicht ist: " + infos.get(end).weight);
}
private void copy(Graph target, Graph source) {
    List<Vertex> vs = source.getVertices();
    List<Edge> es = source.getEdges();
    vs.toFirst();
    es.toFirst();
    while(vs.hasAccess()) {
      target.addVertex(vs.getContent());
      vs.next();
    }
    while(es.hasAccess()) {
      target.addEdge(es.getContent());
      es.next();
    }
}
private Graph retrace(Graph g, Map<Vertex, DijkstraData> infos, Vertex end) {
    Graph res = new Graph();
    Vertex old = end;
    Vertex parent = infos.get(old).previous;
    old.setMark(true);
    copy(res, g);

    while(parent != null) {
      Edge edge = g.getEdge(parent, old);

      parent.setMark(true);
      edge.setMark(true);

      old = parent;
      parent = infos.get(parent).previous;
    }
    return res;
}