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

Gerichtete Graphen:

anchored to [[111.00_anchor]] proceeds from [[111.13_Graphen_basics]]

bb

Overview:

Wir haben zuvor primär ungerichtete Graphen betrachtet, also solche, bei welchen wir nur schauen, ob eine Verbindung zwischen besteht oder nicht. Wir möchten jetzt noch gerichtete Graphen ( oder auch Netzwerke genannt) betrachten, welche neben diesen Verbindungen noch speichern werden in welche Richtung sie verbunden sind.

Definition:

[!Definition] Gerichtete Graphen was zeichnet einen gerichteten Graphen (netzwerk) aus? #card Sei ein Graph $G=(V,E)$ gegeben. Weiterhin führen wir eine Funktion für die Kantenkosten $c:E⟶\mathbb{R}$ Wir bezeichnen jetzt die neue Struktur als netzwerk bzw. (gerichteten Graphen): $$G=(V,E,c)$$ ![[Pasted image 20231117163323.png]] ^1704708751267

Kosten eines Pfades:

Da wir jetzt neue Wichtungen einfügen, können wir auch die Kosten erweitern. Während wir zuvor nur den Betrag eines pfades betrachtet haben, der angab, wie viele Knoten bei diesem traversiert werden, möchten wir jetzt noch die Kosten unter Betrachtung der Kantenkosten definieren.

[!Definition] Kantenkosten in gerichteten Graphen: wie definieren wir die Kosten? #card Sei ein Graph gegeben: $G=(V,E,c)$. Wir definieren jetzt einen Pfad $Pfad(v_0,v_1,\dots ,v_n)$ Wir notieren die Kosten dessen folgend: $c(v_1,v_1,\dots ,v_n):=\sum _{i=1}^{n}c(v_{i-1},v_i)$ –> Wir ziehen hier schauen hier also, jeweils die Kosten zwischen der einzelnen Knoten an und werden anschließend diese Kosten summieren (obviously) ^1704708751276

Betrachtung in gerichteten Graphen

Wir können bei Gerichteten Graphen, wie auch bei ungerichteten Graphen, nach speziellen Pfaden suchen. Genauer möchten wir uns jetzt aber mit Shortest Paths auseinandersetzen, also solche Pfade in Graphen die etwa zwei Punkte miteinander verbinden.

Single Source Shortest Paths:

Wir betrachten einen Graph $G=(V,E,c)$. Weiterhin setzen wir jetzt $s\in V$ als einen Startpunkt in unserem Graphen ( wir möchten von diesem aus einen anderen Knoten erreichen.) Wir möchten auch noch einen Zielpunkt $u\in V$ definieren, welchen wir also von $s$ aus erreichen möchten.

Wir betrachten jetzt alle Pfade von $s⟶u$, also $Pfad(s,u)$. Wir definieren folgende Definition, um die kürzesten Pfade zu finden / bestimmen: $$\gamma (u):=\{\begin{array}{ll}\infty & \text{falls gilt}P(s,u)=\varnothing \\ & \\ inf(c(p)|p\in P(s,u))& \text{sonst}\end{array}$$ Finden wir einen Pfad $p_s=Pfad(s,u),c(p_s)\le 0$, dann nennen wir diesen :: einen negativen Zykel –> also ein Pfad, der scheinbar negative Wichtung hat, und somit eventuell zuu günstig sein würde / kann ( sie sollten nicht existieren xd) ^1704708751285

Folgerung aus $\gamma (u)$

Aus der Funktion $\gamma (u)$, wie obig definiert erfahren, wir ob ein Pfad existiert oder nicht: wann finden wir einen, wann nicht?

• wenn die Menge der Pfade zwischen den zwei Punkten $=\varnothing$ ist, dann haben wir keinen legitimen Pfad gefunden
• Wenn ein / oder mehrere Pfade existieren, dann wird die Funktion $\gamma (u)$ garantiert den kürzesten Pfad finden –> weil wir aus der Menge das Inferium entnehmen!

Wir können hier aber auch noch spezielle Eigenschaften betrachten:

[!Important] Ist $\gamma (u)=-\infty$ Was folgt? #card Dann haben wir einen negativen Zykel, mit welchem der Pfad bzw. Zusammenschluss der beiden Knoten möglich ist.

Dieser ist unendlich, weil wir hier wahrscheinlich den Zykel unendlich mal laufen würde ( denn jedes mal werden die Kosten dann kleiner!) und sich somit die Kosten immer weiter verringern ^1704708751293

[!Tip] ist $\gamma (u)\in \mathbb{R}$ was wird impliziert? #card Dann existiert ein billigster Weg zwischen $s⟶u$ mit den entsprechenden Kosten $\gamma (u)$ Also wir können sichergehen, dass wir einen kürzesten Pfad gefunden haben, wenn Elemente haben, die $\in \mathbb{R}$ liegen ^1704708751301

DAG $⟹$ topologische Sortierung

Mit einem DAG meinen wir einen Directed Acyclic Graph [[111.13_Graphen_basics#Acyclic Graphs]]. Also einen Graphen, der gewichtetet ist, keine ZYkel zwischen Knoten aufweist.

Wir können genau diese Implikation folglich prüfen, indem wir einen Algorithmus dafür konzipieren:

Distanzen d(s) = 0, Pfad(s) = (s) // Initialisierung
for all ( v in V(without s))
	d(v) = infinity // Setze Distanz auf unendlich!

for (v = s+1 to n){ // wir gehen alle Knoten nach S durch
	d(v) = min(d(u)+c(u,v) | (u,v) in E): // wir suchen die minimale Distanz verfügbar und setzen diese Distanz für den Knoten
	Pfad(v) = verbinde( Pfad(u),v) // Zusammenfügen der beiden Pfade zu einem neuen Pfad, der dem Ziel näher kommt
}

Wenn wir diesen Algorithmus ausgeführt haben gilt für unseren Graphen:

[!Definition] Abschluss des geringsten Pfades zwischen $s$ und allen Vektoren $u$ was gilt? #card Es folgt aus der Abfolge des Algorithmus folgend: $d(v)=\gamma (v),\forall v\in V$ Also wir haben die kürzeste Distanz zwischen jedem Knoten von $s$ nach $u$ in unserem Graph. ^1704708751307

Beweis der Korrektheit der topologischen Sortierung:

Wir können den zuvor definierten Algorithmus unter Betrachtung einer Fallunterscheidung auf Korrektheit prüfen: wie? #card $$\begin{array}{rlr}v<s:& & \gamma (u)=\infty -d(v)\text{ es existiert kein Pfad zwischen beiden}\\ v\ge s:& & \text{ Beweis durch Induktion:}\\ & & \\ IA:& & i=0:\gamma (s+i)=\gamma (s)=0=d(s)=d(s+i)\\ IV:& & \text{gelte folgend }\gamma (s+j)=d(s+j),\forall j<i\\ IS:& & \gamma (s+i)=\min \{\gamma (v)+c(v,s+i)\}\\ & & \min \{\gamma (v)+c(v,s+i)\}\\ & & \min \{d(v)+c(v,s+i)\}\\ & & d(s+i)\end{array}$$ Was unserer Annahme entspricht und somit übereinstimmt, denn wir haben bei Existenz eines Pfades definitiv den kleinsten ausfindig gemacht.! ^1704708751314

DAG prüfen | Laufzeit:

Wir können aus der Betrachtung des Algorithmus und des Beweises dessen Korrektheit

Wir können hieraus folgend ein Lemma bilden:

[!Definition] $d(v)<\infty ⟹$ impliziert? #card Sofern wir den Algorithmus ausführen können wir folgend resultieren: $$d(v)<\infty ⟹Pfad(v)\text{ ist der billigste Weg von }s⟶v$$ ^1704708751320

Weiterhin können wir aus diesem Lemma folgern:

[!Important] $d(v)<\infty ⟹Pfad(v)\text{ ist der billigste Weg von }s⟶v$ was könnenn wir daraus folgern #card Wir können gerne noch ausführen: $$d(v)=\gamma (v)\forall v\in V$$ Weiterhin können wir so auch sagen: $$c(Pfad(v))=d(v)⟹c(Pfad(v))=\gamma (v)$$ ^1704708751326

DAG Findung | Laufzeit

Es lässt sich aus dem obig definierten Algorithmus noch eine Laufzeit bestimmen:

[!Definition] Laufzeit wie können wir sie definieren, wovon hängt sie ab? #card Betrachten wir die Summe der eingehenden Knoten für einen Knoten $v$. Es folgt hier heraus: $$\sum _{v\in V}(|InAdj(v))|⟺\sum _{v\in V}(indeg(v))=\mathcal{O}(m)$$ Wir sehen hier, dass die Konkatenation mit $\mathcal{O}(1)$ durchgeführt wird und sich somit herauskürzen lässt.

Wir können die Distance-Werte folgend mit $\mathcal{O}(n+m)$ beschreiben Die Pfade lassen sich mit $\mathcal{O}(n)$ notieren. ^1704708751333

Satz | Single Source Shortest Paths Zeitaufwand

Wir können aus der obigen Betrachtung notieren, mit welcher Geschwindigkeit SSSP auf einem azyklischen Netzwerk ausgeführt werden kann.

[!Definition] SSSP auf DAG wie schnell? #card Distanzen von SSSP - Single Source Shortest Paths können bei azyklischen Netzwerken in einer Zeit von $\mathcal{O}(n+m)$ berechnet werden. ^1704708751339

Weitere Betrachtung:

Es gibt diverse Implementationen, um SSSP entsprechend finden zu können. Bekannt und einfach wäre dabei [[111.22_Graphen_SSSP_dijkstra]]

Single Source Shortest Paths mit negativen Zykel

Zuvor, etwa in [[111.22_Graphen_SSSP_dijkstra]], haben wir nur DAGs betrachtet, die keine negativen Werte bzw Zykel hatten. –> Würden wir diese zulassen, dann würde der Algorithmus einfach immer durch den Zykel traversieren, um so die kürzesten Kosten ( negativ) zu finden / umzusetzen.

Motivation für Bellman Ford:

Wir möchten jetzt einen Algorithmus betrachten, der es ermöglicht in einem Graphen, der negative Zykel aufweist, einen kürzesten Pfade zu finden. Das steht im Kontrast zu [[111.22_Graphen_SSSP_dijkstra]], weil bei diesem notwendig ist, dass keine negativ gewichteten Zykel auftreten / vorhanden sein dürfen. Wir werden dafür Bellman-Ford betrachten, welcher netterweise direkt für alle Knoten den kürzesten Pfad sucht und findet!

| Definition | Bellman/Ford

[!Important] Intuition für Bellman-Ford welche Grundidee haben wir für den Bellman-Ford Algorithmus ? #card wir möchten bei Bellman-Ford iterativ die Lösung finden / uns dieser annähern. Dafür nutzen wir iterativ die Funktion $Relax(v,w)$, wobei da dann immer $d(w)=min\{d(w),d(v)=c(v,w)\}$ -> Also wir nehmen das Minima der folgenden bekannten Distanzen:

• die Distanz des derzeit besten Pfades $d(w)$
• die Distanz des derzeitigen Vektors und die Kosten, um von $d(v)+c(,w)$ v nach w zu kommen. ^1704708751344

Relaxation orientiert sich dabei an einem mathematischen Vorgehen, um Probleme in kleinere aufzuteilen here more

Wir können daraus folgende Beobachtungen ziehen:

[!Definition] Beobachtungen: was können wir im Bezug auf die Relax-Operation beim Bellman-Ford algorithmus wahrnehmen ? #card Die Relax-Operation erhöht erstmal keinen Distance-Wert, denn sie evaluiert nur! Auch nach der Relax-Operation gilt dann noch $d(v)\ge \gamma (v)$, wenn es zuvor schon galt! ^1704708751351

Wir möchten noch den ungefähren Ablauf des Bellman-Ford Algorithmus betrachten / besprechen

[!Tip] Intuition von Bellman-Ford Algorithmus #card Wir haben also einen Graphen $G$ welcher gewichtet ist und eine Menge von Knoten mit $V$ beschreibt. Wir möchten jetzt hier von unserem Startknoten $s$ die kürzesten Wege von allen Knoten im Graphen berechnen ( was mehr oder weniger automatisch passiert). Dafür initialisieren wir folgend: -> Die Distanz aller Knoten, die nicht $s$ sind, werden auf $\infty$ gesetzt ( also ihre Distanz ist unbekannt / unendlich) Die Distanz des Startknotens setzen wir auf 0 Jetzt werden wir jede Verbindung von $u⟹v$ betrachten und dabei schauen, ob die neue Distanz besser (also kürzer) ist, als die vorherige. ^1704708751357

[!Important] Finden eines negativen Zykel wie finden wir einen? #card

Wir können einen negativen Zykel erkennen, wenn eine neu berechnete Distanz plötzlich kürzer ist, als die vorherige. Wir haben ja immer den derzeitig kürzesten Pfad von einem Knoten $v$ gespeichert und somit würde ein neuer kürzester Pfad bedeuten, dass wir einen übersehen haben oder einen neuen gefunden haben –> also er beste Weg ist kürzer geworden –> negativer Zykel tritt auf! ^1704708751363

Lemma |

Sei $w\in V$ und weiterhin gilt, dass $\delta (w)<\infty$. Sei jetzt $(v,w)$ die letzte Kante auf dem billigsten Pfad von $s⟶w$. Dann gilt jetzt folgend: -> Falls $(v,w)$ relaxiert wird ( also wir die Eigenschaft prüfen, und ferner anpassen, dass die Distanz anders /kürzer ist) und hier auch $d(v)=\delta (v)$ galt, dann wird anschließend: $$d(w)=\delta (w)$$ sein, also wir haben einen neusten kürzesten Pfad gefunden / evaluieren können.

PseudoCode

Betrachten wir jetzt den Algorithmus, der diese Funktionalität beschreiben kann, Wie bauen wir Bellman Ford auf? #card

for all (v in V) 
	d(v) = infinity
d(s) = 0 // initialisiere starwert 

for ( i = 1; i< n-1;++){
	for all ((v,w ) in E) {  // traversiere alle Kanten, die wir kennen
		Relax(v,w) // Prüfe also, ob wir einen besseren Pfad gefunden haben oder nicht 
	}
}

Anders beschrieben auch:

InitializeSingleSource(G,s) --> Setze Distanz aller auf infinity, auser Startknoten, Distance(s)=0
// berechne shortest path
for i = 1, ..., |V|-1 // |V| beschreibt hier n!
	for all edges(u,v) in E // also alle Verknüpfungen iterieren
		Relax(u,v)
// test for cycle in the graph:
for all edges(u,v) in E
	if v.dist > u.dist + w(u,v)
		return false // because after ordering before there **should not be** anything left that could result with a shorter distance

return true

Wir meinen hier mit Relax eine oft genutzt Funktion, welche folgend beschrieben wird: –> [[111.16_Graphen_relaxation|Relaxation]]

Folgerung | Pfade der Länge $i$:

Da wir in diesem Algorithmus Schritt für Schritt die Menge aller Vektoren durchgehen, können wir in bestimmten Zuständen des Algorithmus Aussagen darüber treffen, ob Pfade einer gewissen Länge existieren.

[!Definition] Pfade der Länge $i$ was gilt, und warum? #card Für $i=0,\dots ,n-1$ gilt folgendes: Nach der Phase $i$ ist $d(w)=\delta (w)$ für alle $w\in V$ bei welchen es einen günstigsten Pfad $s⟶w$ mit einer Länge $i$ gibt! ^1704708751369

Wir möchten diese Aussage noch beweisen können:

Beweis von [[#Folgerung Pfade der Länge $i$]]

Wir können es per vollständiger Induktion beweisen. Sei hierfür: $i=0d(s)=\delta (s)=0$ ( also kein negativer Zykel!)

Jetzt zeigen wir, dass $i+1⟶i$ Hierbei ist w der Knoten mit dem billigsten Weg der Länge $i+1$, wobei seine letzte Kante $(v,w)$ ist. ( also irgendein Vektor $v$ bildeten einen Pfad zu diesem). Es gibt hier also einen billigsten Weg von $s⟶v$ nach $i$ Schritten! Er hat also die Länge $=i$

Gemäß der Induktionsannahme gilt nach der Phase $i$ dann folgend $d(v)=\delta (v)$ und folgend dann in Phase $i+1$ wird diese Verbindung von $v⟶w$, also $(v,w)$ relaxed. Dadurch folgt dann: $$d(w)=min\{d(v)+c(v,w)\}=\delta (v)+c(v,w)=\delta (w)$$ Und damit haben wir die Bedingung erfüllt.

[!Definition] Distanz aller Knoten nach $n-1$ Iterationen welchen Zustand haben wir dann? #card Unter Anwendung des Algorithmus werden wir erkennen, dass dieser nach Phase $n-1$ ( also nachdem wir ihn auch terminieren, weil alles erledigt ist) folgende Eigenschaft für alle Knoten erfüllt: $$\forall v\in V:d(v)=\delta (v)$$ ^1704708751375

[!Definition] Zeitaufwand von Bellman-Ford wie zusammengesetzt? #card Wir beschreiben die Laufzeit folgend mit: $$\mathcal{O}(n\cdot m)\vee \mathcal{O}(|V|\cdot |E|)$$ Wobei wir mit n = $|V|$, also die Menge von Knoten meinen! Und weiterhin meinen wir mit $m=|E|$, also die Menge von Kanten, die unser Graph aufweist. ^1704708751383

Beispiel:

[!Question] Betrachten wir folgenden Graphen, wie können wir ihn entsprechend lösen? ![[Pasted image 20231122232620.png]] #card ![[Pasted image 20231122232641.png]] -> Wenn wir hier die Grauen Kanten updaten, werden wir die Shortest-Paths ( die gespeichert wurden mit [[111.16_Graphen_relaxation]]) aktualisieren. ^1704708751389

Negative Zykeln:

Bei negativen Zykel werden sich die Distanzen immer weiter erniedrigen, weil dieser immer der kürzeste Pfade sein wird ( wird ja mit jeder Iteration kleiner).

[!Definition] Bellman-Ford erweitern, dass er diese erkennen kann wie? #card Wir möchten folgend ein Prozedere einbringen, was eventuell dabei hilft, dass wir mit negativen Zykeln umgehen können.

1. Führe zuerst $n-1$ Phasen von Bellman-Ford aus. Wir merken uns dabei immer den Distanz-Wert von ($d_1$)
2. Wir werden jetzt noch n-Phasen ausführen und daraus einen neuen Wert $d_2$ erhalten. Jetzt betrachten wir diese beiden Werte ( wir haben also ein richtiges Ergebnis, nachdem wir den Algorithmus abgeschlossen haben, nach (n-1) Schritten) –> der zweite Wert ist quasi ein Vergleich nach weitere Betrachtung ( er sollte eigentlich nicht mehr kleiner werden, weil wir ja schon das minima gefunden haben müssten) Es folgt jetzt: $$d_2(w)=d_1(w)⟹d_1=\delta (w)\text{ also es ist der ku¨rzeste Pfad, der sich nicht mehr a¨ndert!}$$ und weiter auch: $$d_2(w)<d_1(w)⟹\delta (w)=-\infty \text{ also wir haben scheinbar einen ku¨rzeren Pfad gefunden, was nicht sein kann}$$ –> Es folgt aus letzterem dann, dass es ein negativen Zykel geben muss! ^1704708751395

Motivation Floyd/Warshall

Wir möchten jetzt noch betrachten, wie wir für alle Paare in einem Graphen den kürzesten Pfad evaluieren und definieren können. Dafür möchten wir einen Algorithmus einführen, der besagte Information für einen Graphen ohne negative Zykel berechnen kann.

| All Pairs Shortest Paths |

Wir setzen einen gerichteten Graphen $(V,E,c)$ voraus, welcher keine negativen Zykel aufweist. Ferner sind dann die Knoten $V=\{1,2,\dots ,n\}$.

[!Important] Definition der kürzesten Pfade zwischen $i,j$ #card Wir definieren für beliebige Knoten $i,j$, sowie $0\le k\le n$ die Kosten, die für den Pfad ${\delta }_k(i,j)$ aufgebracht werden müssen. Das heißt wir beschreiben damit den günstigsten Weg von $i⟶j$ mit den inneren Knoten zwischen $0,\dots k$ –> also die Knoten, die existieren im Graphen ^1704708751404

[!Example] Finden von Kosten für Pfade: Unter Betrachtung des folgenden Graphen: ![[Pasted image 20231122234626.png]] Was sind die kürzesten Pfade für: ${\delta }_0(1,4)$ ${\delta }_2(1,4)$ ${\delta }_4(1,4)$ #card ${\delta }_0(1,4)=\infty$ ${\delta }_2(1,4)=6$ also von 1->2->4 (Knoten = 2) -> wir erlauben nur die Knoten von 0-2 ${\delta }_4(1,4)=1$ also von 1->3->4 –> wir erlauben alle Knoten von 0-4! ^1704708751410

Wir möchten jetzt entsprechend ${\delta }_k(i,j)$ berechnen können.

Für $k=0$ gilt initial: ${\delta }_0(i,j)\{\begin{array}{ll}c(i,j)& \text{ falls }(i,j)\in E\\ 0& \text{ falls }i=j\\ \infty & \text{ sonst}\end{array}$

Aus dieser Definition möchten wir jetzt eine entsprechender Beschreibung schaffen:

[!Definition] Zustände und Beschreibung dieser von ${\delta }_k(i,j)$ #card Ferner gilt dann für k=n: ${\delta }_n(i,j)=\delta (i,j)=\text{ Kosten des gu¨nstigsten Weges}i⟶j$ –> Also wenn wir unendlich viele Knoten zulassen, wird halt der kürzeste genommen!

Wir können das jetzt noch rekursiv beschreiben: $${\delta }_k(i,j)=\min (\{{\delta }_{k-1}(i,j),{\delta }_{k-1}(i,k)+{\delta }_{k-1}(k,j)\})$$ Wir können es folglich noch visualisieren: ![[Pasted image 20231122235846.png]] ^1704708751417

Definition | Floyd/Warshall |

[!Important] Intuition für Floyd/Warshall #card Wir möchten annehmen, dass alle Kanten beschriftet sind ( dabei Chronologische Reihenfolge!) Wir möchten zwei Knoten spezifisch betrachten ( Start und Endpunkt) und dann schauen, wie wir ihn erreichen können, wenn wir eine bestimmte Menge von den beschrifteten Knoten erlauben. Also erlauben wir etwa alle Knoten von $0,\dots ,5$ und schauen, ob wir dann eine Distanz zwischen den beiden Knoten haben (können). Wir möchten jetzt von unten nach oben, die einzelnen kürzesten Pfade finden und dann aufbauen / bzw einen passenden, kurzen Pfad konstruieren.

Aus der vorherigen Betrachtung [[#All Pairs Shortest Paths]] können wir jetzt den Floy/Warshall-Algorithmus konstruieren lassen.

[!Example] Ein mögliches Beispiel von Floyd/Warshall in der Anwendung: ![[Pasted image 20231123000741.png]]

[!Definition] Pseudocode für Floyd/Warshall

n:= number of vertices (Knoten)
D^(0) = W # Also eine n,n Matrix wobei sie Diagonal 0 ist und sonst unendlich ( Pfad von sich selbst ist immer 0)
# Begin algorithm
for k=1,...,n # also alle Ziffern der Knoten durchlaufen
  Let D^k be a new n,n-matrix
  
  for s =1, ..., n
  		for t=1,...,n
  			d_k(s,t) - min{ d_k-1 (s,t) , d_k-1 (s,k) + d_k-1(k,t) }
  			# wir schauen, ob ein konstruierter Pfad mit Zwischenschritten kürzer sein wird oder nicht 
  			# ist er kürzer, setzen wir dann den Eintrag d_k(s,t) entsprechend neu!
  return D^n

Was speichern wir jetzt in $D_k(s,t)$? –> Es wird hier die derzeitige Distanz, zwischen s und t in der Iteration von $k$ beschrieben / gespeichert.

Wir können ihn auch noch anders darstellen ( wie bei Kaufmann):

# initialize
for all (i!=j, in V){
	if(  falls (i,j) in E ):
		distance_0(i,j) = c(i,j)
	else:
		distance_0(i,j)= infinity son
}
for all (i=j) {
	distance_0(i,j)=0
}
# initialization done

for (k=1 to n){
	   for all (i,j in V){
		   distance_k(i,j) = min{ distance_k-1(i,j), distance_k-1(i,k) + distance_k-1 (k,j) } 
		   #also wir setzen ggfs eine neue kürzere Distanz, wenn die Verbindung von (i,k)->(k,j) kürzer also der zuvor gespeicherte Wert!
	}
}

[!Definition] Laufzeit von Floyd/Warshall Wir können sehen, dass die Laufzeit von Floyd-Warshall durch drei Schleifen läuft, welche bis zu $n$-Iterationen haben. Es folgt daher: $$\mathcal{O}(n^3)$$

Wir können noch für die modifizierten Kosten $c^{\prime }$ folgern:

[!Definition] $Pfadp$ ist der kürzeste. was können wir sagen, wenn wir einen kürzesten Pfad $p$ erhalten haben? #card $\forall u,v\in V$ ist der Pfad $p$ zwischen $u,v$ der günstigste Weg für ein originales $c$ (also unverändert). $⟺$ $\pi$ ist der günstigste Weg für die Kosten $c^{\prime }$! ^1704708751423

Wir betrachten dafür die korrekte Wahl / Findung der Kantenkosten $c^{\prime }$: Wir wählen dafür $c^{\prime }(u,v)=c(u,v)+h(u)-h(v)$ für beliebige Kanten $(u,v)\in E$ und weiterhin ist $h:V⟶R$ Jetzt können wir den Pfad $p$ folgend beschreiben: $$\begin{array}{rl}p& =(v_0,\dots ,v_k)\\ c^{\prime }(p)& =\sum _i{c}^{\prime }(v_i,v_{i+1})\\ & =\sum _{i}c(v_i,v_{i+1})+h(v_i)-h(v_{i+1})\\ & =c(p)+h(v_0)-h(v_k)\end{array}$$ Es folgt hieraus, dass $$c(p)=\delta (v_0,v_k)⟺c^{\prime }(p)=\delta (v_0,v_k)+h(v_0)-h(v_k)$$ und für den Fall, dass es ein Zykel ist, gilt dann: $v_0=v_k:=c(p)=c^{\prime }(p)$

Wir müssen jetzt entsprechend $h$ wählen, damit $c^{\prime }\ge 0,\forall (u,v)\in E$

Wir erweitern $G$ hiermit mit einer neuen Quelle $s\notin V$ und somit auch einer neuen Kante $(s,v),\forall v\in V:c(s,v)=0$ Wir berechnen jetzt den SSSP von s aus und setzen dabei $h(v)=\delta (s,v),\forall v\in V$

[!Important] Es folgt hieraus jetzt $h(v)\le h(u)+c(u,v),\forall (u,v)\in E$ Daraus folgt dann: $0\le c(u,v)+h(u)-h(v)=c^{\prime }(u,v)$

[!Warning] Wir könne $h$ folglich dann mit: Bellman/Ford und Dijkstra berechnen:

1. mit Bellman Ford folgt: $\mathcal{O}(nm)$
2. mit Dijkstra folgt: $\mathcal{O}(n\cdot \log n+m)$

[!Definition] Zeitkomplexität von APSP? #card Wir können das APSP - All shortest paths problem - mit einem Zeitaufwand von $\mathcal{O}(n^2\cdot \log n+nm)$ beschreiben ^1704708751429

Alternative Konstruktion zu Floyd/Warshall:

Statt Floyd-Warshall, welcher sehr langsam ist $\in n^3!$, können wir einfach $n$-mal einen anderen Algorithmus anwenden.

Wir haben hier zwei Möglichkeiten:

$n\times$ Bellman-Ford

Konstruktion wie bauen wir den auf? #card Hierbei möchten wir jeden Knoten mindestens einmal als die Quelle $s$ definieren ( weswegen wir $n$-mal ausführen). Es ergibt sich eine Laufzeit von $\mathcal{O}(n\cdot n\cdot m)$
^1704708751435

$n\times$ Dijkstra

Konstruktion wie können wir diesen jetzt aufbauen, was ist zu beachten? #card Wir können jetzt einfach $n$-mal Dijkstra ausführen und dabei jeden Knoten einmal als Quelle, also $s$ definieren. (Es ist quasi analog zu [[#$ntimes$ Bellman-Ford]]) Achtung–> wir müssen hierbei unbedingt nichtnegative Kanten haben, sonst wird Dijkstra nicht funktionieren. Es ergibt sich folgende Laufzeit $\mathcal{O}(n\cdot (n\cdot \log n+m))$ ^1704708751441