DAA - Kürzeste Wege

Dijkstra-Algorithmus

Der Dijkstra-Algorithmus löst das Problem der kürzesten Wege aus einer Hand in einem gerichteten gewichteten Graphen G = (V, E) , wobei alle Kanten nicht negativ sind (dh w (u, v) ≥ 0 für jede Kante (u, v) ) Є E ).

Im folgenden Algorithmus verwenden wir eine Funktion Extract-Min(), der den Knoten mit dem kleinsten Schlüssel extrahiert.

Algorithm: Dijkstra’s-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
S := Ф 
Q := G.V 
while Q ≠ Ф 
   u := Extract-Min (Q) 
   S := S U {u} 
   for each vertex v Є G.adj[u] 
      if v.d > u.d + w(u, v) 
         v.d := u.d + w(u, v) 
         v.∏ := u

Analyse

Die Komplexität dieses Algorithmus hängt vollständig von der Implementierung der Extract-Min-Funktion ab. Wenn die Funktion zum Extrahieren von min mithilfe der linearen Suche implementiert wird, ist die Komplexität dieses AlgorithmusO(V² + E).

Wenn wir in diesem Algorithmus Min-Heap verwenden, auf dem Extract-Min() Funktion gibt den Knoten von zurück Q Mit dem kleinsten Schlüssel kann die Komplexität dieses Algorithmus weiter reduziert werden.

Beispiel

Betrachten wir den Scheitelpunkt 1 und 9als Start- bzw. Zielscheitelpunkt. Zu Beginn sind alle Scheitelpunkte außer dem Startscheitelpunkt mit ∞ und der Startscheitelpunkt mit gekennzeichnet0.

Scheitel	Initiale	Schritt 1 V 1	Schritt 2 V 3	Schritt 3 V 2	Schritt 4 V 4	Schritt 5 V 5	Schritt 6 V 7	Schritt 7 V 8	Schritt 8 V 6
1	0	0	0	0	0	0	0	0	0
2	∞	5	4	4	4	4	4	4	4
3	∞	2	2	2	2	2	2	2	2
4	∞	∞	∞	7	7	7	7	7	7
5	∞	∞	∞	11	9	9	9	9	9
6	∞	∞	∞	∞	∞	17	17	16	16
7	∞	∞	11	11	11	11	11	11	11
8	∞	∞	∞	∞	∞	16	13	13	13
9	∞	∞	∞	∞	∞	∞	∞	∞	20

Daher der minimale Abstand des Scheitelpunkts 9 vom Scheitelpunkt 1 ist 20. Und der Weg ist

1 → 3 → 7 → 8 → 6 → 9

Dieser Pfad wird basierend auf Vorgängerinformationen bestimmt.

Bellman Ford Algorithmus

Dieser Algorithmus löst das Problem des kürzesten Wegs einer einzelnen Quelle eines gerichteten Graphen G = (V, E)bei denen die Kantengewichte negativ sein können. Darüber hinaus kann dieser Algorithmus angewendet werden, um den kürzesten Weg zu finden, wenn kein negativ gewichteter Zyklus existiert.

Algorithm: Bellman-Ford-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
for i = 1 to |G.V| - 1 
   for each edge (u, v) Є G.E 
      if v.d > u.d + w(u, v) 
         v.d := u.d +w(u, v) 
         v.∏ := u 
for each edge (u, v) Є G.E 
   if v.d > u.d + w(u, v) 
      return FALSE 
return TRUE

Analyse

Der Erste for Die Schleife wird für die Initialisierung verwendet, die in ausgeführt wird O(V)mal. Der nächstefor Schleife läuft |V - 1| geht über die Kanten, die dauertO(E) mal.

Daher läuft der Bellman-Ford-Algorithmus ein O(V, E) Zeit.

Beispiel

Das folgende Beispiel zeigt Schritt für Schritt, wie der Bellman-Ford-Algorithmus funktioniert. Dieser Graph hat eine negative Flanke, aber keinen negativen Zyklus, daher kann das Problem mit dieser Technik gelöst werden.

Zum Zeitpunkt der Initialisierung sind alle Eckpunkte außer der Quelle mit ∞ und die Quelle mit gekennzeichnet 0.

Im ersten Schritt werden alle Eckpunkte, die von der Quelle aus erreichbar sind, zu minimalen Kosten aktualisiert. Daher Eckpunktea und h werden aktualisiert.

Im nächsten Schritt Scheitelpunkte a, b, f und e werden aktualisiert.

Nach der gleichen Logik werden in diesem Schritt Eckpunkte verwendet b, f, c und g werden aktualisiert.

Hier Eckpunkte c und d werden aktualisiert.

Daher der minimale Abstand zwischen dem Scheitelpunkt s und Scheitelpunkt d ist 20.

Basierend auf den Vorgängerinformationen lautet der Pfad s → h → e → g → c → d