cards-deck: 100-199_university::111-120_theoretic_cs::111_algorithms_datastructures

Dijkstra Algorithmus

anchored to [[111.00_anchor]]

Overview:

Mit Dijkstra können wir SSSP in einem gewichteten Graphen, welcher positive , nicht negative Kanten aufweist.

Definition:

[!Definition] Intuitive Betrachtung Dijkstra #card Prinzipiell möchten wir uns Schritt für Schritt von unserem Punkt zu unserem Zielpunkt bewegen. Dabei arbeiten wir uns so voran, dass wir mit jeder Iteration immer den bestmöglichen Knoten ( bzw günstigsten) übernehmen möchten. Dabei ist wichtig, dass diese Knoten nur angrenzend sein können. Sie müssen also Nachbarn von den bereits gefundenen Knoten ( die wir dann aufgenommen und evaluiert haben) sein.

Mit dieser Prämisse werden wir uns Schritt für Schritt immer den günstigsten Weg suchen, können dabei aber auch keinen finden, wenn denn kein Weg zwischen $u⟶v$ existiert ( aber dann wäre die Anwendung auch sinnfrei) ^1704708859613

Der Algorithmus setzt bestimmte Mengen, die wir während des Ablaufes betrachten müssen, voraus. Wir definieren sie folgend:

[!Definition] Dijkstra Voraussetzung welche Mengen brauchen wir? #card Wir starten immer an einem Knoten $s$, welcher als unser Startpunkt deklariert ist Wir werden nun eine Menge $S=\{v\in V|d(v)=\delta (v)\}$ und weiter $S^{\prime }=\{v\in V\setminus S|v\text{ hat Nachbar in}S\}$

Intuitiv heißt es also, dass wir eine Menge von Knoten haben, die wir schon kennen. Sie befinden sich in $S$. Jetzt werden wir sukzessive S vergrößern, indem wir einen benachbarten Knoten nehmen ( welcher die geringste Distanz zu unserem Ziel haben soll!) und ihn der Menge hinzufügen. Dabei werden wir immer die derzeitige Distanz als Gewicht des Knotens speichern. So können wir immer das minimum anvisieren! ^1704708859624

| Algorithmus

Unter dieser Betrachtung müssen wir jetzt folgend agieren: wie?, was ist notwendig,um von $s$ nach $p$ zu kommen? #card Wir vergrößern jetzt nach und nach $S$ sukzessive, bis wir $S=V$, dabei möchten wir immer den besten Pfad in jedem Schritt gehen. Das ganze können wir auch in einem PseudoCode beschreiben:

S = {s}, 
d(s), // Initial-Kosten wird aus dem Startknoten genommen
d'(s) = 0
^1704708859630

S' = OutAdj(s) // also alle **Knoten**, die von unserem Startpunkt erreicht werden können!
for all u in S':
	d'(u) = c(s,u) // wir setzen also die Distanz, um von s nach u ( also alle Knoten, die angrenzend sind) zu kommen gleich mit den Kosten dieses Pfades.
for all u in V\(S' und {s}):
	d'(u) = infinity // wir setzen die Distanz aller Knoten, die wir noch nicht besucht haben, auf unendlich 
	// ( weil wir später immer den kleinsten Knoten heraussuchen werden und es somit ermöglicht wird!)

while (S != V){
	w = min(S')  // wähle den Knoten in der Menge von angrenzenden Knoten, der die geringsten Kosten hat!
	d(w) = d'(w) // wir setzen die Kosten des Knotens auf seinen realen Wert ( weil wir ihn schon besucht haben jetzt)
	S = S und {w} // Knoten ist jetzt bekannt
	S' = S'\{w}  // Knoten muss nicht mehr besucht werden
	
	for all (u in OutAdj(w)){ // wir gehen also alle Nachbarn von dem Knoten e durch
	}
		if (u not in (S und S')):
			S' = S' und u // wenn also der neue Nachbar noch nicht bekannt oder entlang der Grenze ( die mit S' beschrieben wird) verläuft / verfügbar ist
		d'(u) = min(d'(u), d'(w)+c(w,u)) // wir suchen den minimalen Wert für die Distanz
		// wir vergleichen, ob der Pfad, den wir schon haben bis zu u kürzer ist, als die vorhandene Distanz von u selbst
}

| Korrektheit

Wir möchten für die Anwendung von Dijkstra ein Lemma setzen:

[!Definition] Lemma | Korrektheit von Dijkstra warum ist er korrekt? Wie beweisen wir es? #card Wird $w\in S^{\prime }$ gewählt, sodass $d^{\prime }(w)$ minimal ist ( also die Distanz). dann folgt daraus: $d^{\prime }(w)=\delta (w)$

Beweis: Wir können die Aussage folgend beweisen: Sei $p=(s,s_1,\dots ,s_k,w)$ der derzeit billigste Weg von $s⟶w$, mit $s_i\in S$. Dann können wir jetzt annehmen, dass ein billigerer Weg existiert, welchen wir mit $q$ definieren möchten. Dabei befindet sich bei diesem Pfad der erste Knoten $v\in V\setminus S$. Da es ein billigerer Weg ist, muss gelten: $$d^{\prime }(v)\ge d^{\prime }(w)$$ Es gilt jetzt aber auch: $$c(q)\ge d^{\prime }(v)\ge d^{\prime }(w)=c(p)$$ denn alle Kantenkosten sind nichtnegativ. Dies führt zu einem Widerspruch! ^1704708859636

Laufzeit:

Die Laufzeit von Dijkstra hängt stark davon ab, wie wir die Menge $S,S^{\prime }$, sowie die Menge der gespeicherten Distanzen $d,d^{\prime }$ umsetzen. ( denn diese sind wichtig und somit Indikatoren, ob unsere Implementation gut funktionieren wird oder nicht )

[!Important] Implementation von $S,S^{\prime },d,d^{\prime }$ wie sollten wir diese implementieren? #card Man könnte / sollte hierbei $S,S^{\prime }$ als Bitvektoren mit der Länge $|V|$ beschreiben und die Distanz-Werte $d,d^{\prime }$ mit einem Integervektor der Länge $|V|$ ^1704708859643

Daraus lässt sich nun auch die Laufzeit berechnen:

[!Definition] Laufzeit für Dijkstra wovon ist sie stark abhängig? wie durchlaufen wir die Knoten? #card for all $(u\in OutAdj(w){)}^{\prime }=\mathcal{O}\left(\sum _{w}OutDeg(w)\right)=\mathcal{O}(n+m)$ -> wir durchlaufen also die gesetzte Adjazenzliste. Wir haben weiterhin eine $n\times \text{Minimumssuche in }{S}^{\prime }$, wodurch wird bei dieser Operation mit $\mathcal{O}(n^2)$ resultieren

Es ergibt sich nun folgende Laufzeit: $$\mathcal{O}(n^2+m)$$ ^1704708859648

Aber wir können die Laufzeit nochmals verbessern:

[!Important] Verkürzung der Laufzeit auf $\mathcal{O}(n\log n+m\log n)$ was benötigen wir dafür? #card Man kann die Minimumssuche in $\mathcal{O}(\log n)$ umsetzen, sofern man $S^{\prime }$ als einen Heap aufbaut [[111.09_heaps#Running time|consider running time]] -> Dadurch wird das Einfügen, die Minimumssuche und das Löschen in $\mathcal{O}(\log n)$ umgesetzt.

Wir müssen hier dennoch imemr $d^{\prime }$-Werte verringern ( was im Heap etwas langsamer war). Aber dennoch geht das gut.

Wir resultieren hiermit mit der Laufzeit von $\mathcal{O}(n\log n+m\log n)$ ^1704708859654

Folgerung Geschwindigkeit:

[!Definition] In welcher Zeit können wir einen SSSP in einem nicht-negativen, gerichteten Graphen berechnen? #card Wir können einen Single Source Shortest Path in einem gerichteten Graphen mit nichtnegativen Kantenkosten in folgender Zeit berechnen: $$\mathcal{O}(n+m)\log n$$

Weiterhin wäre es auch in $\mathcal{O}(n\log n+m)$ möglich! ^1704708859661