public void sssp(int node){ NodeListQueued l = new NodeListQueued(); int[] distance = new int[this.numberOfNodes]; for (int i = 0; i < this.numberOfNodes; i++) distance[i] = this.numberOfNodes;
l.addElement(new Integer(node)); distance[node] = 0; while (!l.isEmpty()){ int i = ((Integer) l.firstElement()).intValue(); l.removeFirstElement(); Enumeration enum = this.successors(i); while (enum.hasMoreElements()) { int j = (Integer enum.nextElement()).intValue(); if (i != j && distance[j]==this.numberOfNodes){ l.addElement(new Integer(j)); distance[j] = distance[i]+1; } } } // Hier noch Ausgabe einfügen }
Berechnung der Kürzesten Wege
E v v Î ) , ( ´ ´´ Sind die Distanzen gegeben, kann man für einen beliebigen v´ Knoten sehr einfach den kürzesten Weg zu dem Ausgangsknoten v berechnen.
Hierzu gehen wir von v´ einfach zu dem Knoten v´´ mit , der den geringsten Abstand zu v hat.
Dann bestimmen wir den kürzesten Weg von v´´ zu v.
Sind wir bei v angelangt, so stoppen wir.
So erhalten wir rückwärts den kürzesten Pfad von v nach v´.
Gewichtete Graphen
Gewichtete Graphen unterscheiden sich von ungewichteten dadurch, dass jede Kante mit einer reellen Zahl bewertet ist.
Diese Gewichte werden als Distanzen oder Kosten für das Traversieren interpretiert.
Wir setzen im Folgenden voraus, dass diese Gewichte nicht negativ sind, d. h., dass es eine Abbildung c : E R0+ gibt, die jeder Kante ein nicht-negatives Gewicht zuordnet.
Das Problem, für einen Knoten die kürzesten Wege zu allen anderen Knoten zu berechnen wird dadurch schwieriger.
Allerdings lassen sich die Grundideen aus dem ungewichteten Fall übernehmen.
Optimalitätsprinzip: Für jeden kürzesten Weg p = (v0, v1, . . . , vk) von v0 nach vk ist jeder Teilweg p´ = (vi, . . . , vj), 0 i j k ein kürzester Weg von vi nach vj .
Begründung:
Wäre dies nicht so, gäbe es also einen kürzeren Weg p´´ von vi nach vj , so könnte auch in p der Teilweg p´ durch p´´ ersetzt werden und der entstehende Weg von v0 nach vk wäre kürzer als p.
Dies ist aber ein Widerspruch zu der Annahme, dass p ein kürzester Weg von v0 nach vk ist.
Folgerung (1)
Damit können wir länger werdende kürzeste Wege durch Hinzunahme
einzelner Kanten zu bereits bekannten kürzesten Wegen mit folgender
Invariante berechnen: Für alle kürzesten Wege sp(s, v) und Kanten (v, v´) gilt:
c(sp(s, v)) + c((v, v´)) c(sp(s, v´)):
Für wenigstens einen kürzesten Weg sp(s, v) und eine Kante (v, v´) gilt:
c(sp(s, v)) + c((v, v´)) = c(sp(s, v´)):
Folgerung (2)
Sei p = (v0, v1, . . . , vk) ein Weg von v0 nach vk ist.
Sei p´´ ein kürzerer Weg von vi nach vj als der entsprechende Teilweg in p.
Dann können wir in p den Teilweg von vi nach vj durch p´´ ersetzen, um einen kürzeren Weg p´ von v0 nach vk zu erhalten.
Idee des Verfahrens von Dijkstra
Anfangs ist die Entfernung d(v) aller von s verschiedener Knoten .
Die Entfernung von s von sich selbst ist natürlich 0.
Wir betrachten eine Menge PQ von Knoten-Entfernungs-Paaren (v, d(v)), die wir mit {(s; 0)} initialisieren.
Dann wird PQ nach dem Prinzip ”Knoten mit kürzester Distanz von s zuerst“ schrittweise bearbeitet, bis PQ leer ist: 1. Entferne Knoten v aus PQ mit minimaler Distanz d(v) von s, d(v) ist der kürzeste Distanz von s nach v. 2. Für jeden Knoten w V mit (v,w) E verfahre wie folgt: (a) Falls (w, d(w)) PQ, ersetze (w, d(w)) durch (w, min{d(w); d(v) + c(v,w)}). (b) Falls w nicht in PQ enthalten ist, füge (w, (d(v) + c(v,w)) in PQ ein.
Benötigte Datenstrukturen
Wir merken uns für jeden Knoten v die bisher berechnete, vorläufige Entfernung d(v) zum Anfangsknoten s.
Weiter speichern wir den Vorgänger von v auf dem bisher berechneten vorläufig kürzesten Weg.
Weiter benötigen wir eine Datenstruktur, um die noch zu bearbeitenden Knoten zu speichern. Dazu verwenden wir eine Priority Queue.
Priority Queues (Vorrangwarteschlangen)
Als Priority Queue bezeichnet man eine Datenstruktur zur Speicherung einer Menge von Elementen, für die eine Ordnung (Prioritätsordnung) definiert ist, so dass folgende Operationen ausführbar sind: Initialisieren (der leeren Struktur),
Einfügen eines Elementes,
Minimum suchen,
Minimum entfernen,
Herabsetzen der Priorität eines Schlüssels.
Offensichtlich hängt die Rechenzeit von Dijkstra’s Algorithmus von der Implementierung der Priority Queue ab.
Wenn wir eine lineare Liste zur Speicherung der Priority Queue PQ verwenden, so benötigen einzelne Operationen, wie z.B. das Auffinden des Minimums das Einfügen oder das Herabsetzen der Priorität O(|V |) Schritte.
Auch wenn wir die Elemente in der Liste sortieren, benötigen wir noch Linearzeit für das Herabsetzen der Priorität.
Da wir O(|V |) Schleifendurchläufe auszuführen haben, ist der Gesamtaufwand O(|V |2).
Eine bessere Datenstruktur für Dijkstra’s Algorithmus ist ein so genannter Fibonacci-Heap.
Damit erreicht man eine Gesamtlaufzeit von O(|E| + |V | log |V |).
Comments