WEBVTT 00:06.190 --> 00:11.010 Herzlich willkommen zur Vorlesung Algorithmen. 00:12.030 --> 00:15.150 Dann schauen wir doch mal, was haben wir uns letztes Mal in der 00:15.150 --> 00:16.090 Vorlesung angeschaut. 00:16.330 --> 00:24.270 Wir sind letztes Mal bei den Graph Algorithmen geblieben, hatten uns 00:24.270 --> 00:29.230 noch mal etwas exotischere Graph-Repräsentationen angeschaut und 00:29.230 --> 00:33.250 danach war der Großteil der Vorlesung zu Graph Traversierung. 00:34.550 --> 00:40.530 Also der Frage, wenn Sie einen Graph gegeben haben, wie können Sie die 00:40.530 --> 00:45.570 Knoten des Graphen durchlaufen, sodass Sie eben jeden Knoten 00:45.570 --> 00:49.590 garantiert einmal betrachten oder erreichen. 00:50.490 --> 00:54.090 Und da haben wir uns verschiedene Varianten angeschaut, die sich in 00:54.090 --> 00:57.550 der Reihenfolge unterscheiden, wie diese Knoten besucht werden. 00:58.710 --> 01:03.170 Einerseits war es die Breitensuche, also wo man versucht hat, 01:04.370 --> 01:08.810 ausgehend von einem Startknoten, alle Knoten in einer bestimmten 01:08.810 --> 01:10.230 Entfernung schrittweise zu finden. 01:10.410 --> 01:13.970 Also wir haben begonnen, die Knoten, die Schritt 1 entfernt sind, zu 01:13.970 --> 01:14.330 sammeln. 01:15.030 --> 01:17.130 In einer Queue haben wir das gemacht und dann von da aus eben 01:17.130 --> 01:22.290 weitergehend die Knoten, die in zwei Schritten vom Startknoten aus 01:22.290 --> 01:25.230 erreicht sind und haben somit eben so schrittweise die Knoten 01:25.230 --> 01:28.650 eingesammelt, bis wir irgendwann mal alle Knoten gefunden hatten. 01:30.070 --> 01:36.650 Die zweite Variante war die Tiefenzuche und bei der Tiefenzuche, was 01:36.650 --> 01:37.350 war da der Unterschied? 01:37.670 --> 01:43.930 Wir sind dabei nicht in der minimalen Entfernung zum Startknoten die 01:43.930 --> 01:48.470 Knoten abgelaufen, sondern haben stattdessen uns auf einen Pfad 01:48.470 --> 01:51.390 konzentriert und sind den Pfad so weit wie möglich gelaufen und haben 01:51.390 --> 01:54.750 dann eben mit Backtracking weitere Pfade betrachtet, bis wir auch 01:54.750 --> 01:56.130 wieder alle Knoten erreicht hatten. 01:58.010 --> 02:02.230 Gut, das war die Tiefenzuche und die Tiefenzuche hat uns erlaubt auch 02:02.230 --> 02:08.250 bestimmte Zusatzinformationen zu berechnen, die zum Beispiel für eine 02:08.250 --> 02:12.810 topologische Sortierung der Knoten wichtig ist. 02:15.010 --> 02:20.150 Okay, also wenn wir noch mal schauen, wir hatten diese Breitensuche, 02:20.710 --> 02:24.810 diese Breadth-First-Search und die Tiefenzuche, die Depth-First 02:24.810 --> 02:25.250 -Search. 02:26.330 --> 02:30.150 Dieser Algorithmus für die Breitensuche war nicht rekursiv, sondern 02:30.150 --> 02:35.770 hat mit zwei Queues gearbeitet, die eben schrittweise die aktuelle 02:35.770 --> 02:40.270 Tiefe im Baum durchsucht haben und die Ergebnisse dann in eine zweite 02:40.270 --> 02:42.610 Queue geschrieben haben, die die nächstgrößere Tiefe waren. 02:48.170 --> 02:51.410 Vorwärtskanten konnten damit nicht identifiziert werden, aber dafür 02:51.410 --> 02:54.770 konnten die kürzeste Wege in einem Graph gefunden werden, weil wir ja 02:54.770 --> 02:58.110 eben immer schrittweise in zunehmender Entfernung die Knoten 02:58.110 --> 02:59.030 abgearbeitet haben. 03:00.730 --> 03:04.870 Dann bei der Tiefenzuche war es so, dass wir keine zusätzlichen 03:04.870 --> 03:07.830 Datenstrukturen verwendet haben, wie diese beiden Queues zum Beispiel 03:07.830 --> 03:11.750 bei der Breitensuche, sondern nur den Rekursionsstapel. 03:12.690 --> 03:17.590 Deshalb ist es ein etwas einfacherer Algorithmus gewesen und dieser 03:17.590 --> 03:21.290 dient auch als Grundlage für weitere Algorithmen. 03:21.590 --> 03:24.150 Einen davon hatten wir schon betrachtet, das war eben diese 03:24.150 --> 03:25.430 topologische Sortierung. 03:28.270 --> 03:33.630 Gut, wir haben uns in dem Zusammenhang auch angeschaut, was passiert, 03:33.730 --> 03:36.950 wenn der Graph in unabhängige Komponenten zerfällt. 03:38.350 --> 03:41.870 Also wenn man vom Startknoten aus jetzt nicht alle Knoten erreichen 03:41.870 --> 03:45.150 kann, sondern wenn es eine zweite Komponente gibt, die überhaupt nicht 03:45.150 --> 03:48.510 mit der ersten verbunden ist, dann erreichen wir die über einen Pfad 03:48.510 --> 03:49.130 natürlich nicht. 03:49.250 --> 03:52.010 Und dann hat man nochmal einfach eine Schleife außenrum nochmal gelegt 03:52.010 --> 03:56.490 über unseren Algorithmus, der dann eben noch nicht besuchte Knoten 03:56.490 --> 03:59.890 oder einen dieser nicht besuchten Knoten als neuen Startknoten gewählt 03:59.890 --> 04:03.490 hat und dann von dort ausgehend wieder eine Breiten- oder Tiefenzuche 04:03.490 --> 04:04.350 durchgeführt hat. 04:05.890 --> 04:09.510 Aber ich möchte jetzt einfach der Vollständigkeit halber nochmal diese 04:09.510 --> 04:13.870 Begriffe des Zusammenhangs oder Zusammenhangskomponenten nochmal kurz 04:13.870 --> 04:18.010 wiederholen, weil es da auch zwei verschiedene Varianten gibt. 04:18.170 --> 04:22.550 Eben einmal der Zusammenhang in ungerichteten Graphen und die 04:22.550 --> 04:24.730 Zusammenhangskomponenten in gerichteten Graphen. 04:26.430 --> 04:29.290 Und das, was ich jetzt gerade beschrieben hatte, dass so ein Graph 04:29.290 --> 04:31.630 komplett zerfällt in unabhängige Teile. 04:32.250 --> 04:36.550 Das ist das, was man im Normalfall bei ungerichteten Graphen sich 04:36.550 --> 04:37.150 anschaut. 04:38.170 --> 04:43.190 Und da ist dann der Begriff des Zusammenhangs so definiert, dass ein 04:43.190 --> 04:46.770 Graph G zusammenhängt, wenn jeder Knoten von jedem anderen erreicht 04:46.770 --> 04:47.370 werden kann. 04:48.970 --> 04:52.370 Also wenn wir uns diesen Graph hier an der rechten Seite, der ja nicht 04:52.370 --> 04:53.470 gerichtet ist, mal anschauen. 04:54.130 --> 04:57.210 Also ist hier jeder Knoten von jedem anderen erreichbar? 04:57.330 --> 04:57.590 Nein. 04:57.750 --> 05:00.430 Zum Beispiel der Knoten 1 ist von gar keinem anderen erreichbar. 05:00.970 --> 05:03.170 Der Knoten 6 ist zum Beispiel auch von null nicht erreichbar. 05:03.310 --> 05:05.970 Das heißt, der ist nicht zusammenhängend, wie man das intuitiv auch 05:05.970 --> 05:06.150 sieht. 05:06.290 --> 05:08.290 Also der besteht einfach aus drei Komponenten. 05:09.910 --> 05:14.030 Und was jetzt hier dann eine Zusammenhangskomponente ist, ist eben 05:14.030 --> 05:16.470 jede dieser einzelnen getrennten Teile. 05:17.050 --> 05:20.210 Und das heißt, man kann das dann formal so definieren, dass das ein 05:20.210 --> 05:24.470 maximal zusammenhängender Teilgraph dieses Gesamtgraphen ist. 05:26.890 --> 05:30.470 Also das 6 und 7 zusammengenommen, wäre zum Beispiel ein 05:30.470 --> 05:33.950 zusammenhängender Teilgraph, weil hier eben innerhalb von diesen zwei 05:33.950 --> 05:38.630 Knoten alle Knoten, die ja eben diese zwei sind, untereinander 05:38.630 --> 05:39.430 erreichbar sind. 05:39.870 --> 05:42.490 Er wäre allerdings nicht maximal, wenn wir ja noch vier dazu nehmen 05:42.490 --> 05:44.510 könnten. 05:44.710 --> 05:46.910 Und die sind dann auch alle untereinander erreichbar. 05:47.030 --> 05:49.210 Das heißt, von vier können wir zum Beispiel über diesen Pfad hier, 05:49.290 --> 05:51.210 über 6 und 7, den Knoten 7 erreichen. 05:52.110 --> 05:54.970 Und das wäre dann eben auch so ein maximal zusammenhängender Graph und 05:54.970 --> 05:57.430 eine Zusammenhangskomponente in einem ungerichteten Graph. 06:00.030 --> 06:03.370 Okay, das ist der Begriff des Zusammenhangs in ungerichteten Graphen. 06:03.450 --> 06:07.590 Und in einem gerichteten Graph, da gab es dann den Begriff der starken 06:08.210 --> 06:08.730 Zusammenhangskomponente. 06:09.810 --> 06:16.490 Und stark zusammenhängend bedeutet dann, dass in einem solchen Graph, 06:16.590 --> 06:20.670 also da haben wir jetzt eben eine Richtung für jede Kante gegeben, für 06:20.670 --> 06:26.110 jedes beliebig gewählte Knotenpaar u, v, es ein Pfad von u nach v und 06:26.110 --> 06:27.910 auch einen Pfad von v nach u gibt. 06:28.770 --> 06:32.490 Das heißt, wir haben die Möglichkeit für zwei beliebig gewählte 06:32.490 --> 06:35.950 Knoten, vom ersten zum zweiten zu kommen und auch wieder vom zweiten 06:35.950 --> 06:37.070 zurück über einen Pfad. 06:38.870 --> 06:42.270 Wenn man sich das jetzt hier unten zum Beispiel wieder anschaut, also 06:42.270 --> 06:45.670 hier oben zum Beispiel, diese drei schwarzen Knoten hier, da haben wir 06:45.670 --> 06:46.850 eben diesen Zyklus. 06:46.990 --> 06:52.410 Das heißt, wir können von jedem Knoten aus die anderen erreichen. 06:52.830 --> 06:55.950 Also zum Beispiel von diesem Knoten den unteren und wir können auch 06:55.950 --> 06:58.610 von hier, von diesem Knoten wieder den oberen erreichen, über diese 06:58.610 --> 06:58.970 Kante. 06:59.390 --> 07:01.970 Das heißt, wir haben hier die Pfade in beide Richtungen und deshalb 07:01.970 --> 07:07.510 wäre dieser Teilgraf stark zusammenhängend. 07:08.350 --> 07:11.110 Genauso dann eben auch dieser Teilgraf, der grüne hier unten, wäre 07:11.110 --> 07:12.310 auch stark zusammenhängend. 07:14.210 --> 07:17.670 Und was man sieht jetzt ist, dass dieses starke Zusammenhang bei 07:17.670 --> 07:21.430 gerichteten Grafen bedeutet jetzt eben nicht, dass wenn wir eine 07:21.430 --> 07:25.730 solche Komponente haben, dass dieser Graf in komplett unabhängige 07:25.730 --> 07:29.150 Komponenten zerfällt, sondern wir haben wirklich einfach nur Bereiche, 07:29.810 --> 07:32.690 die zwar noch mit dem restlichen Graf verbunden sein können, aber 07:32.690 --> 07:36.010 innerhalb eines solchen Bereichs oder einer solchen starken 07:36.010 --> 07:38.270 Zusammenhangskomponente sind eben alle Knoten untereinander 07:38.270 --> 07:39.270 erreichbar. 07:41.090 --> 07:42.750 Das ist dieser starke Zusammenhang. 07:44.430 --> 07:47.850 Und auch ähnlich wie jetzt mit dieser Zusammenhangskomponente wird 07:47.850 --> 07:50.890 jetzt dann die starke Zusammenhangskomponente so definiert, dass es 07:50.890 --> 07:53.810 ein maximal stark zusammenhängender Teilgraf ist. 07:54.910 --> 07:58.370 Also wenn man sich hier zum Beispiel anschaut, dieser Teilgraf, der 07:58.370 --> 08:02.370 zum Beispiel nur diese Knoten hier enthalten würde, wäre ja auch stark 08:02.370 --> 08:05.310 zusammenhängend schon, aber er ist eben nicht maximal, wenn man noch 08:05.310 --> 08:08.490 diesen oberen Knoten, diesen hier noch mit dazu nehmen könnte. 08:09.130 --> 08:12.210 Und dann ist er maximal, weil dann kein weiterer Knoten mehr 08:12.210 --> 08:13.310 dazugenommen werden kann. 08:15.770 --> 08:19.590 Okay, also das sind die starken Zusammenhangskomponenten und dann ist 08:19.590 --> 08:23.170 auf gerichteten Grafen auch noch der Begriff der schwachen 08:23.170 --> 08:26.070 Zusammenhangskomponente oder der Begriff schwach zusammenhängend 08:26.070 --> 08:26.610 definiert. 08:27.370 --> 08:31.130 Und der entspricht dann eigentlich dem, was man einfach ohne diesen 08:31.130 --> 08:34.090 Zusatz stark oder schwach auf ungerichteten Grafen hat. 08:34.770 --> 08:37.370 Und das funktioniert dann so, dass man einfach jetzt hier die Richtung 08:37.370 --> 08:41.190 vergisst von allen Kanten und den einfach den Graf als ungerichtet 08:41.190 --> 08:44.610 betrachtet und dann wieder auf Zusammenhangskomponenten prüft. 08:44.710 --> 08:49.450 Das wäre dann diese schwach zusammenhängende Graf. 08:53.480 --> 08:58.280 Okay, also hier unten rechts zum Beispiel wäre dieser Gesamtgraf jetzt 08:58.280 --> 09:01.100 eben schwach zusammenhängend, weil wir eben, wenn wir den als 09:01.100 --> 09:04.100 ungerichtet betrachten, der nicht in komplett getrennte Komponenten 09:04.100 --> 09:08.300 zerfällt, aber die starken Zusammenhangskomponenten sind eben noch mal 09:08.300 --> 09:10.880 Teilgrafen dieses Gesamtgrafs dann. 09:12.420 --> 09:17.440 Okay, also so weit nochmal, ein bisschen als Wiederholung, die 09:17.440 --> 09:19.360 Begriffe des Zusammenhangs. 09:22.790 --> 09:27.890 Gut, und also vielleicht wollen wir uns jetzt nochmal betrachten, wie 09:27.890 --> 09:31.630 das bei unserem Suchverfahren ausgesehen hat. 09:33.290 --> 09:38.130 Ja, da spielt in erster Linie eigentlich dieser zu starke Zusammenhang 09:38.130 --> 09:41.990 eine Rolle, wobei man jetzt von hier natürlich auch wenn man das Null 09:41.990 --> 09:45.090 zum Beispiel als Startknoten wählen würde, dann ist von hier aus eben 09:45.090 --> 09:48.950 auch kein anderer Knoten erreichbar, weil es hier keine ausgehenden 09:48.950 --> 09:49.590 Kanten gibt. 09:49.850 --> 09:51.270 Also das spielt hier auch ein bisschen mit rein. 09:51.350 --> 09:53.990 Dann müssen wir dann auch, wenn wir jetzt hier bei einer Suche zum 09:53.990 --> 09:57.750 Beispiel diesen weißen Knoten als Startknoten wählen würde, wäre diese 09:57.750 --> 10:01.110 erste Tiefenverbreitensuche bereits abgeschlossen mit dem einen Knoten 10:01.110 --> 10:04.010 und man müsste sich dann irgendeinen anderen wieder auswählen, um von 10:04.010 --> 10:09.030 dort aus diese Tiefenverbreitensuche dann weiter fortzusetzen. 10:10.710 --> 10:12.090 Aus dem Teilgraf. 10:12.570 --> 10:17.190 Also man schneidet irgendeine bestimmte Knotenmenge raus, betrachtet 10:17.190 --> 10:20.490 dann durch diese Teilmenge induzierten Teilgraf. 10:20.630 --> 10:22.970 Das sind dann eben alle Kanten, die innerhalb dieses Teilgrafs 10:22.970 --> 10:26.830 verlaufen und nicht irgendwie nach außen gehen auf irgendeinen Knoten, 10:26.870 --> 10:29.230 der außerhalb dieser isolierten Menge liegt. 10:29.730 --> 10:34.070 Und innerhalb von dieser Knotenmenge plus den sich daraus ergebenden 10:34.070 --> 10:38.910 Kanten, da muss dann eben zwischen beiden beliebig gewählten 10:38.910 --> 10:41.610 Knotenpaare diese fahrtbedingten beiden Richtungen gelten. 10:44.250 --> 10:46.610 Sonst noch Fragen dazu, wenn wir gerade dabei sind? 10:49.090 --> 10:49.690 Nein? 10:50.470 --> 10:54.810 Sonst rufen sie einfach auch rein, wenn sie eine Frage noch haben. 10:57.050 --> 11:05.870 Okay, also soweit noch mal der Rückblick zu den Tiefenbreitensuch- und 11:05.870 --> 11:09.650 was wir uns heute anschauen wollen, ist ein weiterer sehr wichtiger 11:09.650 --> 11:14.570 Algorithmus auf Graphen, nämlich das Suchen und Finden von kürzesten 11:14.570 --> 11:15.430 Wegen in Pfaden. 11:16.570 --> 11:19.710 Und was wir da heute machen werden, ist, dass wir uns einen oder 11:19.710 --> 11:22.390 vielleicht den wichtigsten Algorithmus dazu anschauen, um kürzeste 11:22.390 --> 11:23.610 Pfade in Graphen zu finden. 11:24.070 --> 11:28.390 Das ist der sogenannte Dijkstra-Algorithmus, benannt nach dem 11:28.390 --> 11:31.850 Informatiker Ezra Dijkstra. 11:32.650 --> 11:36.610 Und wir werden uns heute auch noch die Laufzeit dieses Algorithmus 11:36.610 --> 11:41.810 anschauen und etwas analysieren und unter Umständen, wenn wir heute 11:41.810 --> 11:44.750 oder nächstes Mal dann noch eine Variante oder eine Erweiterung dieses 11:44.750 --> 11:48.910 Algorithmus anschauen, den sogenannten Bellman-Ford-Algorithmus. 11:50.250 --> 11:54.950 Aber beginnen wir mit dem Basis-Algorithmus, Dijkstra-Algorithmus und 11:54.950 --> 11:59.630 generell dem kürzeste Wege oder kürzeste Pfade-Problem. 12:01.490 --> 12:02.510 Worum geht es dabei? 12:04.310 --> 12:08.090 Kürzeste Wege zu finden ist etwas, was man eigentlich im Alltag immer 12:08.090 --> 12:11.610 wieder vor genau dieser Aufgabe steht. 12:12.050 --> 12:16.870 Zum Beispiel, wenn Sie jetzt hier in Karlsruhe unterwegs sind und mit 12:18.070 --> 12:21.250 Straßenbahn oder Bus von einem Ort zu einem anderen kommen wollen, 12:21.710 --> 12:23.990 dann stehen Sie da eben auch vor der Frage, ja wie kommen Sie jetzt 12:23.990 --> 12:28.170 von einem Ort, also zum Beispiel, wenn Sie hier unten, ich kann es 12:28.170 --> 12:31.550 jetzt gar nicht lesen, wo wir hier sind, dann in Bühl starten würden, 12:31.950 --> 12:36.510 wie kommen Sie da am schnellsten in einen Ort, hier rechts oben zum 12:36.510 --> 12:36.910 Beispiel. 12:39.870 --> 12:42.950 Und genau die Frage ist schon eben, wie müssen Sie jetzt irgendwelche 12:42.950 --> 12:49.330 Bahnen wählen, wie müssen Sie umsteigen und ja, also man kann jetzt 12:49.330 --> 12:52.350 hier vielleicht auch schon erahnen, dass hier verschiedene Kriterien 12:52.350 --> 12:55.950 eine Rolle spielen können, wie man jetzt einen kürzesten Pfad 12:55.950 --> 12:56.570 definiert. 12:57.390 --> 13:00.410 Also man könnte sagen, es wird wahrscheinlich meistens so sein, man 13:00.410 --> 13:03.070 ist an der Zeit interessiert, also wie komme ich einfach am 13:03.070 --> 13:07.630 schnellsten von einem Ort zu einem bestimmten anderen und dann würde 13:07.630 --> 13:10.750 ich einfach die Zeiten betrachten, die eben die Bahn benötigt, 13:10.990 --> 13:12.850 zwischen jeder Station zum Beispiel. 13:14.350 --> 13:17.290 Könnte auch sein, vielleicht jetzt weniger bei der Bahn, aber wenn Sie 13:17.290 --> 13:20.030 zum Beispiel mit dem Fahrrad oder mit dem Auto unterwegs sind, dass 13:20.030 --> 13:24.850 man vielleicht nach Kilometern kürzeste Strecke interessiert, also 13:24.850 --> 13:28.430 nach der Distanz, das wäre dann ein anderes Kriterium, nachdem man da 13:28.430 --> 13:30.570 immer einen kürzesten Pfad suchen könnte. 13:31.350 --> 13:34.890 Oder zum Teil sind es dann auch Kombinationen aus verschiedenen 13:34.890 --> 13:38.870 Metriken, also wenn Sie jetzt, ich weiß nicht, ob zum Beispiel ein 13:38.870 --> 13:43.030 Routenplaner im Fahrzeug denken oder im Auto, dann ist das unter 13:43.030 --> 13:45.970 Umständen auch eine Kombination aus beiden Kriterien, dass Sie 13:45.970 --> 13:49.680 vielleicht nicht unbedingt die schnellste Strecke haben wollen, wenn 13:49.680 --> 13:51.780 es eine andere gäbe, die eben deutlich kürzer wäre. 13:52.240 --> 13:55.580 Also da kann es sein, dass eine Mischung aus beiden Kriterien dann mit 13:55.580 --> 14:01.980 reinfließt und die bestimmt, was dann eben das Kürzeste dann eben 14:01.980 --> 14:03.280 bedeutet in dem Zusammenhang. 14:05.520 --> 14:08.340 Okay, also die Frage, mit der wir uns jetzt beschäftigen wollen, ist, 14:08.420 --> 14:14.320 wir haben eben zum Beispiel so ein Problem hier gegeben, so ein 14:14.320 --> 14:17.160 Transportproblem, dass wir von einem Ort zum anderen kommen und wir 14:17.160 --> 14:21.780 wollen eben den optimalen Weg finden oder den kürzesten Weg, um von A 14:21.780 --> 14:22.600 nach B zu kommen. 14:23.520 --> 14:27.140 Und wir wollen uns jetzt überlegen, wie da so ein Algorithmus aussehen 14:27.140 --> 14:27.400 kann. 14:29.160 --> 14:31.920 Natürlich werden wir das Ganze wieder abstrahieren, das heißt, wir 14:31.920 --> 14:35.940 werden von bestimmten Gegebenheiten, wie zum Beispiel der Geometrie 14:35.940 --> 14:42.280 hier versuchen, Abstand zu nehmen und das nicht in unsere kürzeste 14:42.280 --> 14:45.960 Wegeberechnung mit einfließen zu lassen, sondern wir wählen einfach 14:45.960 --> 14:47.540 diese Abstraktion eines Graphen. 14:48.360 --> 14:51.120 Das heißt, wir haben dann Knoten gegeben, die zum Beispiel jetzt hier 14:51.120 --> 14:54.900 dann den einzelnen Haltestellen oder Haltestationen einer Bahn 14:54.900 --> 14:58.080 entsprechen können und wir haben Kanten gegeben, die eben anzeigen, ob 14:58.080 --> 15:03.640 bestimmte Punkte von einer Bahn verbunden werden und dann haben wir 15:03.640 --> 15:09.480 bestimmte Kosten oder Zeiten, Entfernungen, die zwischen diesen Knoten 15:09.480 --> 15:09.820 gelten. 15:11.500 --> 15:14.820 Okay, also schauen wir uns an. 15:14.940 --> 15:17.280 Nehmen wir nochmal als Beispiel so ein Problem. 15:17.400 --> 15:22.300 Sie wollen hier von A nach B kommen und suchen jetzt hier wirklich 15:22.300 --> 15:25.300 nach der Distanz, die kürzeste Entfernung, wenn sie das zum Beispiel 15:25.300 --> 15:28.020 zu Fuß laufen wollen oder mit dem Auto abfahren. 15:29.260 --> 15:30.400 Also was haben wir gegeben? 15:30.480 --> 15:34.220 Wir haben einen Graph, der besteht aus, wie üblich, eben aus Knoten 15:34.220 --> 15:40.100 und Kanten und was wir jetzt dazuhaben, ist eine Kostenfunktion, die 15:40.100 --> 15:47.920 uns eben angibt, was zu dieser Distanz an den Kosten dazukommt, wenn 15:47.920 --> 15:49.160 wir eine bestimmte Kante wählen. 15:49.840 --> 15:52.500 Oder man kann auch sagen, das ist ein sogenanntes Kantengewicht. 15:53.400 --> 15:54.340 Also was machen wir? 15:54.760 --> 16:00.580 Wir weisen jeder Kante über diese Kostenfunktion C eine reelle Zahl 16:00.580 --> 16:03.200 zu, die eben zum Entfernung angibt. 16:04.600 --> 16:09.560 Also Kostenfunktion ist immer zwischen zwei Knoten und gibt uns an, 16:10.180 --> 16:13.880 was da eben an Zusatz oder zusätzlichem Aufwand dazukommt, wenn wir 16:13.880 --> 16:15.880 diese Kante durchlaufen. 16:16.460 --> 16:19.180 Also zum Beispiel eine gewisse Zeit oder eine gewisse Entfernung, die 16:19.180 --> 16:22.860 wir dafür benötigen, um von dem Startpunkt der Kante zum Endpunkt der 16:22.860 --> 16:23.540 Kante zu kommen. 16:25.420 --> 16:28.320 Gut, zusätzlich hat man da noch einen gegebenen Startknoten. 16:28.560 --> 16:32.160 Das wäre jetzt bei so einem Routenplanungsproblem eben der Ort, an dem 16:32.160 --> 16:37.260 wir uns gerade befinden oder was der Startpunkt unserer Route ist. 16:37.780 --> 16:43.200 Und von da aus suchen wir dann eben jetzt einen kürzesten Weg zu 16:43.200 --> 16:44.280 irgendeinem anderen Knoten. 16:45.800 --> 16:48.140 Und was wir hier betrachten wollen, ist, dass wir jetzt nicht einen 16:48.140 --> 16:53.020 bestimmten Zielknoten uns direkt zum Start vorgeben, sondern wir 16:53.020 --> 16:58.460 wollen für alle Knoten berechnen, was dorthin der kürzeste Weg ist. 16:59.620 --> 17:01.820 Also das ist jetzt vielleicht in dieser Anwendung nicht das 17:01.820 --> 17:05.240 Natürlichste, dass sie von ihrem Startpunkt aus für alle Orte gleich 17:05.240 --> 17:07.520 wissen wollen, wo kommen sie am schnellsten hin. 17:07.680 --> 17:12.300 Aber das ist eine Formulierung, die in anderen Anwendungen eine 17:12.300 --> 17:15.880 gewisse Rolle spielt und die sich natürlich auch verallgemeinern lässt 17:15.880 --> 17:19.440 oder spezialisieren lässt auf dieses Problem, dass wir nur an einem 17:19.440 --> 17:20.560 Ziel interessiert sind. 17:22.380 --> 17:25.240 Okay, aber jetzt wollen wir davon ausgehen, dass wir eben diese 17:25.240 --> 17:29.780 minimale Distanz für alle Knoten im Graph berechnen wollen. 17:30.700 --> 17:31.640 Also was suchen wir? 17:31.700 --> 17:38.700 Wir suchen ausgehend von dem Startknoten S für einen oder für alle 17:38.700 --> 17:43.840 Knoten V den kürzesten Weg, also den minimalen Weg, da bist du ja auch 17:43.840 --> 17:47.100 das Mühe dafür verwendet für die Funktion, also wir suchen den 17:47.100 --> 17:52.780 minimalen Weg oder den kürzesten Weg, um nach V zu kommen von S aus. 17:54.540 --> 17:56.160 Und was bedeutet jetzt kürzester Weg? 17:56.920 --> 17:58.840 Also das definieren wir hier. 17:59.800 --> 18:05.400 Also der minimale Weg, um zu Knoten V zu kommen, ist das Minimum über 18:05.400 --> 18:11.540 alle Pfade, wobei wir die Kosten dieser Pfade betrachten. 18:12.100 --> 18:15.820 Also wir haben einen Pfad gegeben, der von S nach V führt und wir 18:15.820 --> 18:17.720 betrachten die Kosten dieses Pfades. 18:18.820 --> 18:21.040 Jetzt habe ich die Frage, was sind die Kosten eines Pfades? 18:21.800 --> 18:25.160 Und das sollte hier jetzt definiert sein in der nächsten Zeile. 18:25.700 --> 18:29.700 Also die Kosten von einem Pfad, der ausgehend von dem Startknoten über 18:29.700 --> 18:34.860 die Kante E1, dann über Kante E2 bis zur Kante EK irgendwann mal am 18:34.860 --> 18:40.520 Ziel ankommt, soll einfach die Summe der Kosten dieser Kantenkosten 18:40.520 --> 18:40.900 sein. 18:42.820 --> 18:47.800 Also wir haben zwischen jedem Knotenpaar, das mit der Kante verbunden 18:47.800 --> 18:49.420 ist, haben wir die Kosten für diese Strecke. 18:50.040 --> 18:54.060 Also zum Beispiel, um jetzt von einer Straßenbahnstation zur nächsten 18:54.060 --> 18:58.240 zu kommen, wissen wir, die sind vielleicht 1,2 Kilometer entfernt, die 18:58.240 --> 18:59.180 beiden Stationen. 18:59.580 --> 19:03.240 Und um jetzt fünf Stationen zum Beispiel weit zu kommen, eben so ein 19:03.240 --> 19:07.420 Pfad, der uns zu dem Knoten V führt, würden wir einfach die Kosten für 19:07.420 --> 19:09.020 jede einzelne Teilstrecke aufsummieren. 19:09.360 --> 19:11.380 Also es ist nichts sonderlich überraschend. 19:11.940 --> 19:15.800 Und das sollen dann eben die Kosten eines Pfades sein. 19:16.400 --> 19:20.860 Und was wir suchen, ist jetzt eben dann über alle Pfade, die zu dem 19:20.860 --> 19:24.220 Knoten V führen vom Startknoten aus, die minimalen Kosten. 19:24.920 --> 19:27.060 Das ist das Problem, das wir versuchen zu lösen. 19:28.860 --> 19:31.900 Was man häufig auch noch dazu haben möchte, ist man möchte nicht nur 19:31.900 --> 19:36.160 wissen, was ist denn eigentlich jetzt die minimale Strecke oder was 19:36.160 --> 19:38.580 sind die minimalen Kosten, um ans Ziel zu kommen, sondern man möchte 19:38.580 --> 19:40.280 auch wissen, wie komme ich denn ans Ziel. 19:41.000 --> 19:45.660 Also jetzt einfach nur zu wissen, wenn sie jetzt von hier aus nach 19:45.660 --> 19:49.540 Freudenstadt fahren wollen, dann zu wissen, dass sie das in einer 19:49.540 --> 19:51.280 Dreiviertelstunde vielleicht erreichen können. 19:51.920 --> 19:55.200 Das ist vielleicht nicht alles, was sie an Informationen benötigen, 19:55.280 --> 19:57.280 sondern sie würden auch gerne noch wissen, wie sie denn jetzt wirklich 19:57.280 --> 19:57.920 dahin kommen. 19:58.420 --> 20:01.200 Also welche Bahnen müssen sie nehmen, wo müssen sie vielleicht 20:01.200 --> 20:01.760 umsteigen. 20:02.360 --> 20:06.620 Und das wären eben hier diese geeignete Repräsentation des kürzesten 20:06.620 --> 20:07.000 Pfades. 20:07.280 --> 20:12.200 Also sie wollen auch im Normalfall die Liste der Knoten wissen, über 20:12.200 --> 20:15.700 die sie eben vom Start zu ihrem Zielknoten gelangen auf dem kürzesten 20:15.700 --> 20:16.000 Weg. 20:17.860 --> 20:20.660 Okay, also die Zusatzinformation ist auch noch interessant und die 20:20.660 --> 20:21.500 werden wir gleich sehen. 20:21.620 --> 20:24.660 Die werden die Algorithmen im Normalfall auch alle gleich mit 20:24.660 --> 20:27.180 berechnen, so dass sie eben nicht nur die minimalen Kosten, sondern 20:27.180 --> 20:28.460 auch den Weg dorthin haben. 20:33.050 --> 20:36.490 Eine Anwendung hat man jetzt gerade schon gesehen, eben in der 20:36.490 --> 20:41.490 Routenplanung für Straßennetze, Schienennetze, für das gesamte 20:41.490 --> 20:43.010 Bahnnetz in Deutschland zum Beispiel. 20:44.110 --> 20:49.870 Aber nicht nur in realen Transportsystemen taugt es auf, sondern auch 20:49.870 --> 20:53.050 in Spielen ist es was, was man an manchen Stellen benötigt. 20:54.310 --> 20:58.490 Also wenn sie daran denken, dass sie ein Pac-Man Spiel oder ein 20:58.490 --> 21:01.270 ähnliches haben, wo eben irgendwelche Computergegner gesteuert werden 21:01.270 --> 21:04.610 sollen von innen in ihrem Programm, dann sollen die eben nicht 21:04.610 --> 21:07.630 möglichst, oder sollen die möglichst zielgerichtet laufen und nicht 21:07.630 --> 21:11.030 irgendwie übers Spielfeld, sondern eben möglichst auf die, um ein 21:11.030 --> 21:13.390 bestimmtes Ziel zu erreichen, also um zum Beispiel sie zu fangen. 21:14.210 --> 21:17.850 Und da können dann auch wieder solche kürzesten Wege, Algorithmen eine 21:17.850 --> 21:21.010 Rolle spielen, dass sie eben ihre Computergegner entsprechend steuern 21:21.010 --> 21:23.330 können, dass die eben zielgerichtet 21:26.630 --> 21:28.790 auf einen bestimmten Ort zulaufen. 21:30.010 --> 21:33.470 In Kommunikationsnetzen spielt es auch eine Rolle, also wenn sie ans 21:33.470 --> 21:39.210 Internet denken und sie schicken jetzt zum Beispiel einfach ein IP 21:39.210 --> 21:43.290 -Paket übers Internet weg oder sagen wir vielleicht eine E-Mail, dann 21:43.290 --> 21:47.050 ist eben die Frage, über welche Zwischenrechner kann das übertragen 21:47.050 --> 21:47.350 werden. 21:49.470 --> 21:57.010 Und auch da spielen dann solche minimalen Pfad-Algorithmen wieder eine 21:57.010 --> 22:01.290 Rolle oder kürzeste Wege-Algorithmen, die ihnen dann eben angeben, 22:02.110 --> 22:06.250 wenn jetzt über welche Zwischenstationen zum Beispiel ein bestimmtes 22:06.250 --> 22:07.450 Paket dann geroutet wird. 22:09.550 --> 22:14.750 Und das ist etwas, was eben ja im Internet diese Router oder diese 22:14.750 --> 22:19.230 Randknoten, die Netzwerke verbinden, dann auch eben vornehmen. 22:19.330 --> 22:24.870 Die haben eben Algorithmen eingebaut, die für bestimmte Zielnetze eben 22:24.870 --> 22:28.250 gespeichert haben, wie die am besten zu erreichen sind. 22:28.430 --> 22:32.630 Also was ist da der kürzeste Weg, da dann eben im Normalfall gezählt 22:32.630 --> 22:35.890 in Anzahl von Rechnern, die dazwischen liegen oder sogenannten Hops, 22:36.010 --> 22:38.310 die man eben benötigt, um so ein Paket an ein Ziel zu bringen. 22:39.290 --> 22:42.330 Und das ist etwas, was zum Beispiel dann auch in Internetstandards 22:42.330 --> 22:46.810 definiert ist, wie da so ein Routing stattfindet und wie man mit 22:46.810 --> 22:50.690 welchen Algorithmen da die Wege von den Paketen bestimmt werden 22:50.690 --> 22:51.030 sollen. 22:53.230 --> 22:56.190 Das ist etwas, was auch dann dynamisch abgedeckt werden muss wieder. 22:56.430 --> 22:59.210 Das ist etwas, was wir jetzt hier direkt erstmal nicht berücksichtigen 22:59.210 --> 23:00.790 in der heutigen Vorlesung. 23:01.170 --> 23:03.750 Aber wenn jetzt zum Beispiel ein Rechner ausfällt, dann stehen ja 23:03.750 --> 23:06.070 andere Verbindungen zwischen den Rechnern zur Verfügung. 23:07.170 --> 23:09.670 Ähnlich auch in der Routenplanung, wenn jetzt eine bestimmte Strecke 23:09.670 --> 23:13.650 ausfällt, dann möchten sie unter Umständen auch, wenn die gesperrt 23:13.650 --> 23:16.790 ist, irgendwelche Umstände, wo ich anderen Routen dann berechnen 23:16.790 --> 23:17.070 können. 23:17.190 --> 23:19.950 Das heißt, da ist häufig auch eine gewisse Dynamik damit verbunden. 23:21.270 --> 23:25.290 Oder im noch allgemeinen Fall, wenn sie eben zum Beispiel Staus haben 23:25.290 --> 23:28.510 und eine gewisse Stauprognose machen können, zum Beispiel anhand von 23:28.510 --> 23:31.630 Daten eben von anderen Nutzen, die die Strecke abfahren, dann kann das 23:31.630 --> 23:34.650 auch sein, dass sich da die Kosten für jede Kante im Laufe der Zeit 23:34.650 --> 23:35.130 verändern. 23:35.850 --> 23:39.670 Das eben, um von dem Ort A nach B zu kommen, wenn da eben sehr viel 23:39.670 --> 23:42.470 Verkehr ist, auf einmal die Zeit dann statt zwei Minuten fünf Minuten 23:42.470 --> 23:43.010 beträgt. 23:43.550 --> 23:50.150 Also da hat man auch so ein gewisses Problem, das dynamisch auch lösen 23:50.150 --> 23:50.970 zu können, das Problem. 23:52.250 --> 23:54.850 Aber nicht heute in der Vorlesung, sondern heute geht es nur um ein 23:54.850 --> 23:59.130 statisch gegebenes Netzwerk mit konstant vorgegebenen Kantengewichten 23:59.130 --> 24:03.710 und für diesen ersten Fall wollen wir dann dieses kürzeste Wegeproblem 24:03.710 --> 24:04.130 lösen. 24:06.190 --> 24:10.350 Gut, wenn man es sich jetzt anschaut und das allgemeine Problem, wie 24:10.350 --> 24:13.270 wir es gerade definiert hatten, schauen wir noch mal ganz kurz zurück. 24:13.550 --> 24:18.230 Wir hatten definiert, dass die Kostenfunktion für jede Kante, jeder 24:18.230 --> 24:22.970 Kante, wenn sie eben durchschritten wird, eine reelle Zahl zuordnen 24:22.970 --> 24:23.890 zuordnet. 24:24.510 --> 24:28.290 Und das heißt, diese Zahl, dieses Kantengewicht, das kann auch negativ 24:28.290 --> 24:28.670 sein. 24:29.530 --> 24:31.910 Und es gibt auch bestimmte Anwendungen, in denen das sinnvoll ist, 24:31.910 --> 24:33.970 auch negative Kantengewichte zuzulassen. 24:34.430 --> 24:36.390 Also es ist jetzt nicht in der Routenplanung der Fall. 24:37.090 --> 24:40.070 Also da werden sie nicht, wenn sie eine bestimmte Strecke nehmen, auf 24:40.070 --> 24:43.070 einmal in negativer Zeit die durchlaufen können oder mit einer 24:43.070 --> 24:45.670 negativen Entfernung nachher dann dastehen, sondern das sind immer 24:45.670 --> 24:46.450 positive Zahlen. 24:46.770 --> 24:49.650 Aber in anderen Anwendungen gibt es eben auch negative Gewichte 24:49.650 --> 24:51.230 zwischen Kanten. 24:53.170 --> 24:57.490 Und im blödsten Fall ist es so, dass es sogar negative Kanten sind, 24:58.050 --> 25:01.190 die zu einem negativen Kreis führen. 25:01.510 --> 25:05.450 Das heißt, innerhalb eines Zyklus in ihrem Grav oder eines Kreises in 25:05.450 --> 25:09.070 ihrem Grav ergibt sich beim Durchlaufen dieses Kreises ein negatives 25:09.070 --> 25:09.910 Kantengewicht. 25:11.290 --> 25:14.490 Und wenn sie jetzt den kürzesten Pfad eben suchen, einen, der mit 25:14.490 --> 25:21.010 einem niedrigstmöglichen solchen Gewicht über den Gesamtpfad verbunden 25:21.010 --> 25:23.670 ist, dann haben wir natürlich jetzt hier ein gewisses Problem. 25:24.210 --> 25:27.990 Also wenn sie zum Beispiel jetzt hier von S nach V kommen wollen und 25:27.990 --> 25:32.810 sie haben zwischendrin die Möglichkeit, so einen Kreis zu durchlaufen, 25:33.330 --> 25:38.890 der mit einem negativen Gewicht über diesen Kreis verbunden ist, dann 25:38.890 --> 25:40.270 können sie was machen. 25:40.450 --> 25:44.250 Statt ihn nur einmal zu durchlaufen, können sie den eben ein zweites 25:44.250 --> 25:48.090 Mal durchlaufen oder dreimal und ihr Gewicht für den Pfad wird dadurch 25:48.090 --> 25:48.750 immer geringer. 25:49.430 --> 25:52.010 Das heißt, sie können praktisch, wenn sie jetzt einen kürzesten Weg 25:52.010 --> 25:56.650 suchen, indem sie diesen Kreis so oft wie möglich durchlaufen, ihr 25:58.350 --> 26:04.130 Optimierungsziel beliebig senken oder beliebig diese Kosten negativ 26:04.130 --> 26:04.450 machen. 26:05.510 --> 26:09.250 Also das heißt, sie können da praktisch unendliche negative Kosten 26:09.250 --> 26:12.090 ansammeln, indem sie einfach diesen Kreis oft genug durchlaufen. 26:13.570 --> 26:16.130 Und das ist ein gewisses Problem, wenn man jetzt einen kürzesten Pfad 26:16.130 --> 26:20.670 sucht, weil das häufig dann nicht die gewünschte Lösung ist, dass man 26:20.670 --> 26:24.510 einfach jetzt irgendeinen Pfad mit negativen Gewichten unendlich oft 26:24.510 --> 26:25.050 durchläuft. 26:27.330 --> 26:31.770 Also das heißt, diesen Fall, den werden wir in irgendeiner Form jetzt 26:31.770 --> 26:33.390 erst mal ausschließen wollen. 26:33.690 --> 26:38.130 Also es soll erst mal keine negativen Kreise geben in dem, was wir 26:38.130 --> 26:40.550 jetzt uns für den Algorithmus überlegen. 26:42.950 --> 26:46.570 Gut, dann wollen wir uns noch einen weiteren Spezialfall anschauen. 26:46.850 --> 26:51.870 Und zwar, wenn wir annehmen, dass alle Kantengewichte gleich sind oder 26:51.870 --> 26:52.630 z.B. 26:52.710 --> 26:53.750 alle Kantengewichte 1. 26:55.330 --> 26:58.090 Und in dem Fall haben wir unser Problem schon gelöst. 26:58.630 --> 27:02.250 Dann müssen wir nämlich gar nichts Großes weitermachen, als einfach 27:02.250 --> 27:03.050 eine Breitensuche. 27:04.150 --> 27:07.390 Und wir haben es ja vorhin noch mal kurz angesprochen oder wenn Sie 27:07.390 --> 27:10.090 sich noch mal zurückerinnern, die Breitensuche war ja so, dass die 27:10.090 --> 27:15.450 ausgehend vom Startknoten eben als nächstes sich alle Knoten anschaut, 27:15.610 --> 27:19.650 die in Distanz 1 liegen, dann erst danach die, die in Distanz 2 27:19.650 --> 27:21.930 liegen, dann die in Distanz 3 liegen. 27:21.930 --> 27:25.550 Und die werden eben auch entsprechend dann mit diesen Parent-Kanten so 27:25.550 --> 27:26.030 verbunden. 27:26.570 --> 27:30.310 Das heißt, Sie haben dann schon für jeden Knoten schon die minimale 27:30.310 --> 27:32.590 Entfernung vom Startknoten gefunden. 27:33.690 --> 27:37.570 Also für diesen Spezialfall, wenn alle Gewichte gleich sind, haben wir 27:37.570 --> 27:38.590 das Problem schon gelöst. 27:38.790 --> 27:42.770 Da reicht uns wirklich eine einfache Breitensuche aus und damit können 27:42.770 --> 27:45.790 wir dann das kürzeste Wegeproblem schon lösen. 27:47.470 --> 27:49.010 Aber im Normalfall ist das nicht so. 27:49.270 --> 27:55.850 Also nicht alle Orte sind gleich weit entfernt und nicht jeder Ort ist 27:55.850 --> 27:57.830 in der gleichen Zeit zum Beispiel von einem anderen Ort aus zu 27:57.830 --> 27:58.170 erreichen. 27:58.650 --> 28:01.230 Also müssen wir das irgendwie verallgemeinern. 28:03.770 --> 28:10.910 Und es gibt jetzt eine sehr schöne Möglichkeit, wie man das zum 28:10.910 --> 28:13.490 Beispiel, wenn man basteln wollte, so ein Problem lösen könnte. 28:14.510 --> 28:18.370 Und die Idee dabei ist einfach, also wir wollen jetzt ohne 28:18.370 --> 28:22.390 Rechnungsproblem lösen und bauen unser Modell zusammen, was unserem 28:22.390 --> 28:23.170 Graph entspricht. 28:23.970 --> 28:27.830 Und zwar bauen wir das Modell so zusammen, dass wir einfach die Kanten 28:27.830 --> 28:31.730 durch Fäden ersetzen und die Fäden sollen eben immer genau die Länge 28:31.730 --> 28:34.150 haben, die dem Kantengewicht entspricht. 28:35.150 --> 28:38.030 Also ein Kantengewicht 5 wäre zum Beispiel ein 5 cm langer Faden 28:38.030 --> 28:41.350 zwischen den entsprechenden Knoten und ein Kantengewicht von 10 wäre 28:41.350 --> 28:44.630 eben ein 10 cm langer Faden, den man zwischen den Knoten befestigt. 28:45.970 --> 28:48.550 Also genau, die Kanten ersetzen wir durch Fäden, Kantengewichte 28:48.550 --> 28:52.970 entsprechen dann der Fadenlänge und Knoten sind dann einfach, die 28:52.970 --> 28:56.150 bleiben halt irgendwelche Holzkugeln oder sowas, die wir verwenden 28:56.150 --> 28:56.450 können. 28:56.890 --> 28:58.370 Dann basteln wir das Ganze zusammen. 28:58.830 --> 29:03.270 Wir haben unsere Holzkugel, die mit Fäden verbunden sind und was wir 29:03.270 --> 29:06.630 dann machen ist, dieses Gebilde, was wir dann hier zusammengebaut 29:06.630 --> 29:09.610 haben, das können wir zum Beispiel einfach am Startknoten hochheben 29:09.610 --> 29:11.590 und schauen, was dann passiert. 29:12.790 --> 29:18.290 Und dann entwickelt sich hier eben sowas wie hier und man sieht, also 29:18.290 --> 29:21.050 wenn es jetzt hier verschiedene Pfade zum Beispiel gibt, um zu den 29:21.050 --> 29:26.350 Knoten anzukommen, dann läuft er eben über diese beiden Kanten, die 29:26.350 --> 29:30.030 die kürzeste Gesamtlänge haben. 29:30.370 --> 29:32.850 Wenn es noch einen anderen Faden gäbe, wie zum Beispiel diesen hier, 29:33.390 --> 29:38.530 der eine größere Gesamtlänge hätte, dann sorgt er eben dafür, dass 29:38.530 --> 29:41.770 sich hier wie so eine Schlaufe ergibt, aber eben nicht, dass so ein 29:41.770 --> 29:45.770 Fadesteller über lauter gespannte Kanten verläuft. 29:47.090 --> 29:50.030 Also mit diesem einfachen Modell könnten sie eigentlich schon 29:50.030 --> 29:55.430 herausfinden, wie sie jetzt zum Beispiel kürzestmöglich von M nach S 29:55.430 --> 29:59.530 kommen, indem sie eben immer diese gerade gespannten Kanten 29:59.530 --> 30:02.430 durchlaufen und nicht irgendwelche Umwege, die über solche Schlaufen 30:02.430 --> 30:03.350 nur möglich wären. 30:05.750 --> 30:07.630 Okay, also so können wir das Problem lösen. 30:07.730 --> 30:09.730 Das wäre natürlich auch etwas, was man jetzt versuchen könnte, in so 30:09.730 --> 30:12.870 eine physikalische Simulation zum Beispiel zu gießen und dann hätte 30:12.870 --> 30:17.610 man auch eine Lösung für das kürzeste Pfade- oder kürzeste Wege 30:17.610 --> 30:18.010 -Problem. 30:20.450 --> 30:23.130 Aber der Algorithmus selber, der läuft noch ein klein bisschen anders. 30:24.290 --> 30:25.570 Aber schauen wir uns nochmal an, was haben wir dann? 30:25.610 --> 30:30.330 Wir betrachten also jetzt hier irgendeinen beliebigen Knoten V und für 30:30.330 --> 30:35.770 den Knoten V wollen wir so eine Tiefe dV definieren, die jetzt hier 30:35.770 --> 30:37.430 mit enge Tiefe bezeichnet ist. 30:37.670 --> 30:43.350 Also wenn wir den jetzt hier hochheben an den Punkt M, das wäre dann 30:43.350 --> 30:43.990 die Tiefe 0. 30:46.570 --> 30:50.410 Mit welcher Distanz erreichen wir dann zum Beispiel den Knoten O? 30:50.590 --> 30:53.570 Und das wäre hier eben dann die Tiefe 13, wo wir den Knoten O 30:53.570 --> 30:54.010 erreichen. 30:54.390 --> 30:59.610 Oder hier die Tiefe 11, auf der dieser Knoten eben, wenn wir das an M 30:59.610 --> 31:02.470 hochheben, wo wir den anfinden würden. 31:04.110 --> 31:04.890 Also was haben wir? 31:04.970 --> 31:08.410 Wir haben diese Tiefe dV. 31:09.210 --> 31:14.490 Wir wissen dann, also erstmal, es gibt so einen Pfad, der kürzest 31:14.490 --> 31:18.450 möglich ist, indem wir halt einfach die gespannten oder diese straffen 31:18.450 --> 31:21.210 Fäden ablaufen der Reihe nach. 31:21.630 --> 31:25.570 Und wir wissen auch, dass es keinen kürzeren Pfad gibt, weil eben 31:25.570 --> 31:35.730 sonst ein kürzerer Pfad irgendwie, ja, Kanten es geben müsste, wo 31:35.730 --> 31:42.410 diese, wo diese Fäden einfach reißen würden, wenn wir den durchlaufen 31:42.410 --> 31:42.910 würden. 31:44.670 --> 31:48.950 Also zum Beispiel, wenn das jetzt hier, dieser Pfad, der über L und K 31:48.950 --> 31:55.130 und N hierher kommen würde, wenn das der wäre, der über lauter straffe 31:55.130 --> 31:58.590 Kanten laufen würde, dann wäre eben diese andere Verbindung hier nicht 31:58.590 --> 32:02.610 ausreichend und dann würde dieser Pfad nicht mehr reißen. 32:03.270 --> 32:05.890 Also es ist ein ganz nettes Modell, wo man sehen kann, dass sich das 32:05.890 --> 32:09.190 mit so einem Verfahren auch dieses Problem lösen ließe. 32:11.590 --> 32:15.370 Aber wir wollen einen Algorithmus uns anschauen, der ohne so ein 32:15.370 --> 32:16.830 physikalisches Modell funktioniert. 32:17.590 --> 32:23.470 Und dieser Algorithmus, der ist von Edgar Wiebe Dijkstra erfunden 32:23.470 --> 32:25.790 worden und auch schon relativ früh. 32:26.290 --> 32:29.650 Also das war in den 60er Jahren schon. 32:31.510 --> 32:34.850 Edgar Dijkstra, der ist genau Anfang dieses Jahrhunderts gestorben, 32:34.970 --> 32:37.450 2002, ist 1930 geboren. 32:38.130 --> 32:40.590 Und vielleicht, wenn man sich ein bisschen anschaut, was so Stationen 32:40.590 --> 32:44.070 in seinem Leben waren, also er ist Holländer, wie man dem Namen auch 32:44.070 --> 32:44.910 schon entnehmen kann. 32:46.210 --> 32:52.990 Er hat in den 70er Jahren, 1972, den Turing Award gewonnen, der von 32:52.990 --> 32:57.590 der Association of Computing Machinery, der ACM, eben vergeben wird. 32:58.770 --> 33:01.470 Und um das ein bisschen einordnen zu können, Turing Award ist 33:01.470 --> 33:04.530 eigentlich so der größte oder höchste Informatikpreis, den es 33:04.530 --> 33:08.630 überhaupt gibt und ist ungefähr vergleichbar mit dem Nobelpreis. 33:08.870 --> 33:13.430 Also wenn Sie irgendwann mal den ACM Turing Award bekommen, dann 33:13.430 --> 33:17.270 können Sie da sehr stolz drauf sein. 33:17.410 --> 33:20.570 Das ist dann wirklich wie, wenn Sie den Nobelpreis gewonnen hätten. 33:21.650 --> 33:27.470 Und er hat diesen Preis eben 1972 erhalten für verschiedene 33:27.470 --> 33:28.190 Leistungen. 33:30.030 --> 33:34.190 Und er war auf sehr vielen Gebieten aktiv, also im Bereich der 33:34.190 --> 33:37.670 Betriebssysteme zum Beispiel sehr stark und hat sich da mit solchen 33:37.670 --> 33:40.070 Parallelisierungskonzepten beschäftigt und 33:40.070 --> 33:42.790 Synchronisationsmöglichkeiten. 33:43.550 --> 33:46.810 Also der Begriff des Semaphores, weiß nicht, ob Sie ihn schon mal 33:46.810 --> 33:51.410 gehört haben vielleicht, der steuert eben gewisse Regionen, die in 33:51.410 --> 33:56.690 einem Programm geschützt werden sollen vor gleichzeitigem Zugriff 33:56.690 --> 33:59.830 durch verschiedene Sets, zum Beispiel in der Parallelprogrammierung. 34:00.370 --> 34:02.630 Der geht auf Dijkstra zurück. 34:03.990 --> 34:10.570 Er hat sich mit einer Reihe von Programmierungstechniken eben 34:10.570 --> 34:13.370 beschäftigt für Betriebssysteme, also nicht nur das Semaphore, sondern 34:13.370 --> 34:14.190 auch andere Dinge. 34:14.830 --> 34:22.830 Hat dann auch ein eigenes Betriebssystem entwickelt, das DHE hieß, 34:24.070 --> 34:27.890 also das E steht für die Universität, an der er damals tätig war. 34:27.970 --> 34:30.010 Das war in Niederlanden die Universität Eindhoven. 34:31.470 --> 34:35.490 Und das war das erste Multitasking-Betriebssystem und deshalb waren 34:35.490 --> 34:39.750 eben auch diese Parallelisierungen oder diese Konzepte wie im 34:39.750 --> 34:43.690 Semaphore zum Beispiel wichtig, um dafür zu sorgen, dass eben nicht 34:45.390 --> 34:48.190 fehlerhaft durch zwei Prozesse gleichzeitig auf einen gemeinsamen 34:48.190 --> 34:49.350 Speicher zugegriffen wird. 34:52.630 --> 34:55.290 Also er hat sich auch mit, wie gesagt, mit Programmierthemen 34:55.290 --> 34:55.890 beschäftigt. 34:56.050 --> 34:59.930 Das ist eine Sache, war zum Beispiel diese Diskussion, die in den 70er 34:59.930 --> 35:05.130 Jahren sehr stark lief, als es um verschiedene Programmierparadigmen 35:05.130 --> 35:06.550 oder Programmieransätze ging. 35:07.590 --> 35:10.170 Damals ist auch noch sehr viel in Assembler programmiert worden, aber 35:10.170 --> 35:14.210 auch in anderen Programmiersprachen wie BASIC, falls Sie das noch 35:14.210 --> 35:20.770 kennen, war zum Beispiel so ein Go-To-Statement möglich, mit dem man 35:20.770 --> 35:23.130 eben einfach von einer beliebigen Programmstelle an eine andere 35:23.130 --> 35:27.470 Programmstelle springen konnte und von ihm kommt eben so ein Artikel, 35:28.070 --> 35:30.930 der heißt Go-To-Statement considered harmful. 35:31.970 --> 35:37.270 Also Go-To ist was, was eben als schädlich angesehen wird, worauf man 35:37.270 --> 35:39.170 deshalb eben versichten sollte. 35:41.770 --> 35:45.850 Und der Grund ist, dass das in der damaligen Zeit eben was war, was zu 35:45.850 --> 35:48.130 sehr sehr verworrenem Code geführt hat. 35:48.530 --> 35:51.490 Also wenn man einfach beliebig in dem Code hin und her springen kann 35:51.490 --> 35:55.230 mit Go-Tos, dass man zum Beispiel auf Schleifen verzichtet oder andere 35:55.230 --> 35:59.330 Konzepte, die halt heute zum Programmieralltag gehören und eigentlich 35:59.330 --> 36:00.870 in jeder Programmiersprache vorhanden sind. 36:02.130 --> 36:04.930 Also dass man auf Schleifen verzichtet und stattdessen einfach Go-Tos 36:04.930 --> 36:05.410 verwendet. 36:05.710 --> 36:09.430 Das ist was, was viele Programmierer in der Zeit gerne gemacht haben, 36:09.750 --> 36:12.330 die eben vielleicht auch aus der Assembler-Welt noch gekommen sind, 36:12.690 --> 36:16.130 mit der sie auch sehr effizient Programme schreiben lassen, aber sie 36:16.130 --> 36:19.490 geraten wirklich sehr schnell dazu, dass die eben nicht mehr wirklich 36:19.490 --> 36:21.830 lesbar sind und dass man einfach Spaghetti-Code hat, man kann nicht 36:21.830 --> 36:24.410 mehr nachvollziehen, was macht denn der Code jetzt, wenn wirklich 36:24.410 --> 36:25.990 beliebig da hin und her gesprungen wird. 36:27.430 --> 36:29.050 Also Go-To-Statement considered harmful. 36:30.810 --> 36:37.050 Eine Diskussion, die damals in den 70er-Jahren ungefähr lief, wo es 36:37.050 --> 36:41.610 auch dann, ein Großteil lief auch wieder über die Publikation von 36:41.610 --> 36:45.310 dieser ACM, also die Association for Computing Machinery, die hat 36:45.310 --> 36:51.830 eigene Publikationen, zum Beispiel eine eine monatliche Zeitschrift, 36:51.990 --> 36:54.830 die sich Communications of the ACM nennt. 36:55.710 --> 36:58.290 Also das ist auch heute noch, wird auch heute noch rausgegeben. 36:58.370 --> 37:01.430 Das ist auch aus meiner Sicht eine sehr gute Zeitschrift. 37:01.770 --> 37:04.330 Also wer sich die mal anschauen möchte, gibt es auch in der 37:04.330 --> 37:08.990 Bibliothek, aber die ist eigentlich sehr zu empfehlen, wenn Sie sehen 37:08.990 --> 37:11.030 wollen, was aktuell zum Beispiel auch in der Forschung so passiert. 37:12.430 --> 37:16.490 Gibt es ja in den Communications of the ACM eine Reihe von 37:16.490 --> 37:18.110 Übersichtsartikeln zu aktuellen Themen. 37:19.810 --> 37:23.030 Gut, also er hat sich auf der, beim Betriebsamt beschäftigt mit 37:23.030 --> 37:24.010 Programmiersprachen. 37:25.290 --> 37:28.990 Dort auch speziell mit dem strukturierten Programmieren, was damals so 37:28.990 --> 37:30.290 langsam in Mode gekommen ist. 37:30.890 --> 37:34.730 Also wie gesagt, davor eben das Programmieren mit Flussdiagrammen, Go 37:34.730 --> 37:37.170 -To -Statements, wild hin- und herspringen zwischen verschiedenen 37:37.170 --> 37:37.890 Programmstellen. 37:38.490 --> 37:41.030 Und strukturiertes Programmieren war dann etwas, was in 37:41.030 --> 37:45.350 Programmiersprachen wie zum Beispiel ALGOL, eine Programmiersprache, 37:45.490 --> 37:48.930 die Anfang der 60er Jahre entstanden ist oder auch in Pascal stark 37:48.930 --> 37:51.310 propagiert worden ist. 37:53.290 --> 37:58.530 Und wo eben die Dinge herkommen, die auch in modernen 37:58.530 --> 38:01.450 Programmiersprachen wie C++, Java oder sonstigen enthalten sind. 38:01.810 --> 38:08.630 Eben alles, was mit Schleifen, Strukturen zu tun hat, die eben ein 38:08.630 --> 38:11.830 bisschen über das einfach beliebige Programm-Kontinent-Herspringen 38:11.830 --> 38:12.430 hinausgehen. 38:12.910 --> 38:15.490 Das ist etwas, was dieses strukturierte Programmieren umfasst. 38:17.630 --> 38:21.890 Und was heute eigentlich durch Objekte- orientierung dann erweitert 38:21.890 --> 38:25.770 worden ist und heute eigentlich in sehr vielen Programmiersprachen 38:25.770 --> 38:26.790 eigentlich vorhanden ist. 38:29.510 --> 38:29.710 Okay. 38:30.790 --> 38:33.450 Eine andere Person, die auch sehr stark mit strukturierter 38:33.450 --> 38:37.210 Programmierung in Verbindung gebracht wird, ist Nikolaus Wirth, der in 38:37.210 --> 38:40.030 der Schweiz an der ETH Zürich tätig war, auch zu einer ähnlichen Zeit. 38:40.210 --> 38:42.950 Und die kannten sich beide auch sehr gut, Deixtra und Wirth. 38:44.890 --> 38:48.390 Und die haben eben auch an ähnlichen Dingen gearbeitet. 38:48.750 --> 38:52.590 Bei den Programmiersprachen war es dann eben Algol bei Deixtra und 38:52.590 --> 38:59.930 Pascal und Nachfolgesprachen wie Modulaute Oberon dann bei Wirth. 39:00.690 --> 39:07.630 Und eine Aussage habe ich jetzt gerade noch im Kopf, dass Wirth über 39:07.630 --> 39:12.550 Deixtra mal gesagt hat, dass er in einer bestimmten Zeit, nach dieser 39:12.550 --> 39:19.430 Entwicklung des Betriebssystems, sich entschlossen hat, dass er oder 39:19.430 --> 39:24.290 erkannt hat, aus seiner Sicht, dass er selber nicht teamfähig wäre und 39:24.290 --> 39:27.270 dass er deshalb alle weiteren Entwicklungen seit dieser Zeit in den 39:27.270 --> 39:29.950 70er Jahren nur noch alleine durchführen möchte. 39:30.210 --> 39:31.570 Und das hat er danach wirklich umgesetzt. 39:31.750 --> 39:35.790 Das heißt, er hat danach alle Dinge nur für sich alleine gemacht. 39:35.910 --> 39:40.010 Er war an Universitäten weiter tätig, hat aber zum Beispiel dann auch 39:40.010 --> 39:45.090 nur relativ wenig Doktoranden betreut, aber genau noch eine ganze 39:45.090 --> 39:49.010 Reihe von Themen sehr erfolgreich bearbeitet und wie gesagt eben auch 39:49.010 --> 39:50.950 diesen Turing Award gewonnen. 39:53.910 --> 39:57.930 Gut, aber dieser Herr Deixtra war eben nicht nur in dem Bereich aktiv, 39:58.170 --> 40:01.290 sondern hat sich auch Algorithmen angeschaut. 40:02.790 --> 40:04.710 Ja, vielleicht noch eine ganz kleine Randbemerkung. 40:04.870 --> 40:09.390 Sie kennen vielleicht dieses Dining-Philosopher-Problem, was auch ein 40:09.390 --> 40:13.510 bisschen noch mit Parallelität zu tun hat und da geht es eben auch um 40:13.510 --> 40:18.210 so gewisse Protokolle, wie man sicherstellen kann, dass sich zwei 40:18.210 --> 40:21.350 Prozesse zum Beispiel gegenseitig blockieren, indem sie auf gleiche 40:21.350 --> 40:22.390 Ressourcen zugreifen. 40:23.670 --> 40:26.170 Wer kennt das von Ihnen, dieses Dining-Philosopher-Problem? 40:29.420 --> 40:33.760 Ja, einige von Ihnen, aber relativ wenige. 40:34.100 --> 40:38.080 Es geht darum, dass Philosophen sitzen um einen Tisch, um einen runden 40:38.080 --> 40:42.360 Tisch, sagen wir fünf Philosophen und jeder von diesen Philosophen, 40:42.400 --> 40:46.700 der macht jeden Tag nichts anderes als nachzudenken und irgendwann mal 40:46.700 --> 40:47.260 dann zu essen. 40:48.000 --> 40:53.160 Und wenn er essen möchte, dann nimmt er dazu eben das Besteck auf und 40:53.160 --> 40:54.660 er braucht immer zwei Gabeln. 40:54.860 --> 40:56.420 Das sind etwas ungewöhnliche Philosophen. 40:56.540 --> 40:59.780 Und er nimmt dann eben links und rechts von seinem Teller liegen 40:59.780 --> 41:01.760 jeweils eine Gabel, die muss er beide aufnehmen. 41:02.520 --> 41:05.940 Und jetzt ist das Problem so, dass eben zwischen diesen Philosophen 41:05.940 --> 41:07.340 jeweils immer nur eine Gabel liegt. 41:07.520 --> 41:10.740 Das heißt, wenn jetzt der links sitzende Philosoph die rechte Gabel 41:10.740 --> 41:13.960 nimmt, dann kann der rechts von ihm sitzende diese Gabel nicht mehr 41:13.960 --> 41:15.180 nehmen, weil die schon belegt ist. 41:16.140 --> 41:18.600 Und zum Essen braucht er immer beide Gabeln und jetzt ist eben das 41:18.600 --> 41:21.320 Problem, wie kann das sichergestellt werden, dass keiner der 41:21.320 --> 41:24.300 Philosophen verhungert, dass die anderen Philosophen sich irgendwie 41:24.300 --> 41:29.500 blöderweise so eben absprechen oder zufällig so verhalten, dass eben 41:29.500 --> 41:32.860 ein Philosoph nie zwei Gabeln nehmen kann, weil entweder der links 41:32.860 --> 41:34.580 oder der rechts von ihm gerade am Essen ist. 41:35.620 --> 41:38.060 Und das ist einfach so eine Abstraktion von einem Problem, das eben 41:38.060 --> 41:40.900 bei dieser Ressourcenverwaltung, oder wie man es so genannt hat, 41:41.080 --> 41:43.300 Deadlocks vermeiden kann, auftritt. 41:43.480 --> 41:48.460 Und das ist eben dann so ein kleines Modell, an dem er dann auch eben 41:48.460 --> 41:52.060 seine Lösungsvorschläge dann demonstriert hat für dieses Problem. 41:52.880 --> 41:57.220 Also Dining Philosophers ist heute noch was, was in Betriebssystemen 41:57.220 --> 42:00.120 oder in dieser Ressourcenverwaltung eine Rolle spielt. 42:04.410 --> 42:09.570 Gut, aber wieder zurück zum kürzesten Wegeproblem. 42:10.490 --> 42:14.310 Also da gibt es eben auch dazu einen Algorithmus von dem Herrn 42:14.310 --> 42:19.050 Dijkstra und der funktioniert ein bisschen ähnlich wie das, was wir 42:19.050 --> 42:20.730 bereits bei der Breitensuche gesehen hatten. 42:21.890 --> 42:25.570 Wir haben ja auch gerade zwei Folien zurück auch gesehen, dass gleiche 42:25.570 --> 42:28.730 Kantengewichte bedeutet, dass direkt der Breitenzug-Algorithmus 42:28.730 --> 42:30.170 angewendet werden kann. 42:30.810 --> 42:33.230 Und was wir eben jetzt hier ähnlich verwenden wollen, wie bei der 42:33.230 --> 42:38.410 Breitensuche, ist auch wieder so ein Distanz-Array für jeden Knoten, 42:39.050 --> 42:40.370 also D von V. 42:40.490 --> 42:46.390 Wir haben für jeden Knoten V die Distanz D zum Startknoten und die 42:46.390 --> 42:47.990 kann sich im Laufe des Algorithmus verändern. 42:48.210 --> 42:51.190 Das ist einfach das, was wir aktuell als kürzeste Distanz gefunden 42:51.190 --> 42:55.670 haben und wenn wir noch einen besseren Weg finden, dann kann das eben 42:55.670 --> 42:57.510 noch weiter abgedatet werden. 42:59.190 --> 43:00.450 Und was haben wir da für eine Invariante? 43:01.150 --> 43:05.610 Dieses D von V ist natürlich immer größer gleich das µ von V. 43:06.590 --> 43:08.370 Also überlegen wir uns mal kurz, was war µ von V? 43:08.470 --> 43:15.050 µ von V ist der kürzestmögliche Weg zum Knoten V, also das heißt das 43:15.050 --> 43:19.370 theoretische Optimum und D von V ist das, was wir jetzt gerade aktuell 43:19.370 --> 43:21.130 mit unserem Algorithmus gefunden haben. 43:21.650 --> 43:25.630 Und es kann natürlich nie besser sein als das, was eben das Minimum 43:25.630 --> 43:27.790 einfach mathematisch gesehen ist. 43:28.950 --> 43:30.390 Also deshalb gilt diese Invariante. 43:31.270 --> 43:37.270 Was wir auch ähnlich verwalten, wie bei der Breitensuche, ist dieses 43:37.270 --> 43:43.850 Array Parent von V, mit dem wir eben speichern, was in so einem Baum, 43:43.930 --> 43:47.270 den wir eben aufbauen, wenn das Algorithmus, was da der Vorgänger ist. 43:48.190 --> 43:52.310 Und über dieses Parent V werden wir dann eben jetzt diese kürzesten 43:52.310 --> 43:53.530 Wege abspeichern. 43:54.190 --> 43:59.030 Also der Pfad, der mit geringsten Kosten uns zum Zielknoten V führt, 43:59.490 --> 44:03.750 der ist dann über so eine Kette von diesen Parent-Kanten erreichbar. 44:05.130 --> 44:08.790 Und die Invariante soll dann eben hier sein, dass der aktuell kürzeste 44:08.790 --> 44:13.190 Pfad, der eben uns erlaubt, die bisher gefundene Distanz D 44:13.190 --> 44:18.010 nachzuweisen, dass das über diesen Pfad sichergestellt ist. 44:18.750 --> 44:20.990 Also wenn wir uns rechts im Diagramm anschauen, wir haben den 44:20.990 --> 44:25.030 Startknoten, wir haben jetzt gerade irgendeinen Pfad gefunden zum 44:25.030 --> 44:30.790 Knoten V, der aktuell eben die Distanz D enthält, also die Kosten D. 44:32.090 --> 44:35.470 Dann speichern wir eben diese Kosten ab, die eben die Summe ist von 44:35.470 --> 44:38.750 diesen Kantenkosten, die wir von S nach V auf diesem Pfad haben. 44:39.450 --> 44:43.130 Und eben entsprechend diese Parent-Kanten zeigen uns dann den Weg nach 44:43.130 --> 44:43.390 oben. 44:43.590 --> 44:47.750 Also die drücken aus, was denn genau dieser Pfad jetzt ist, der uns 44:47.750 --> 44:49.870 diese Entfernung D erlaubt. 44:52.190 --> 44:54.150 Gut, dann initialisieren wir das Ganze. 44:54.650 --> 44:57.350 Eigentlich auch so ähnlich, wie wir das von der beiden Züge schon 44:57.350 --> 44:57.610 kennen. 44:58.370 --> 45:02.110 Unser Startknoten hat die Distanz 0, da müssen wir gar keine Kante 45:02.110 --> 45:02.950 dazu durchlaufen. 45:03.910 --> 45:06.730 Dann fügen wir auch hier wieder so eine Parent-Kante von den 45:06.730 --> 45:09.050 Startknoten ein, die ist jetzt da rechts gar nicht eingezeichnet. 45:09.410 --> 45:12.130 Eine Kante, die auf den Startknoten selber geht, also wir haben dann 45:12.130 --> 45:13.850 beim Startknoten selber nochmal so eine Loop drin. 45:15.110 --> 45:18.850 Und für alle anderen Knoten definieren wir erstmal die Entfernung als 45:18.850 --> 45:21.570 unendlich, weil wir bisher eben noch nichts Besseres gefunden haben. 45:22.070 --> 45:25.990 Und den Parent-Knoten als undefiniert, weil wir da auch noch nichts 45:25.990 --> 45:26.490 darüber wissen. 45:27.150 --> 45:29.110 Also soweit initialisieren wir das mal. 45:29.390 --> 45:32.790 Das heißt, wir haben nur von den Startknoten Informationen und jetzt 45:32.790 --> 45:36.330 soll eben unser Algorithmus dann das berechnen. 45:38.930 --> 45:44.190 Und dieser Algorithmus basiert auf einer Kernoperation und die hat 45:44.190 --> 45:45.910 vielleicht ein bisschen einen ungewöhnlichen Namen. 45:46.110 --> 45:48.130 Das nennt sich Relaxieren, diese Operation. 45:49.370 --> 45:50.410 Und was passiert? 45:50.890 --> 45:57.170 Das ist eigentlich die Operation, die abläuft, wenn wir einen besseren 45:57.170 --> 46:03.290 Pfad gefunden haben mit kürzerer Distanz oder weniger Kosten zu 46:03.290 --> 46:04.850 unserem Zielknoten V. 46:05.630 --> 46:12.210 Also wenn wir so eine Situation haben, dass wir die Distanz von Knoten 46:12.210 --> 46:17.810 U irgendwie schon berechnet haben und dann haben wir eben diese 46:17.810 --> 46:21.550 Kantenkosten, die ja durch die Problemstellung gegeben sind, um von U 46:21.550 --> 46:24.590 nach V diese Kante, diese eine Kante abzulaufen. 46:25.230 --> 46:29.270 Wenn diese Kosten jetzt geringer sind als das, was wir bisher als 46:29.270 --> 46:34.790 Kosten oder als Distanz von den Knoten V abgespeichert haben, dann 46:34.790 --> 46:36.790 wissen wir, wir haben jetzt irgendwie einen besseren Weg gefunden. 46:37.910 --> 46:43.630 Also statt dem bisher Erreichten, was eben Distanz D von V hat, haben 46:43.630 --> 46:48.290 wir irgendwas gefunden, was geringere Kosten hat, nämlich nur D U plus 46:48.290 --> 46:49.970 die Kosten von der Kante U V. 46:51.170 --> 46:54.310 Und in dem Fall wollen wir eben ein Update durchführen. 46:54.410 --> 46:59.330 Dann ist eben jetzt dieser Pfad, der über diese Kante U V zu V führt, 46:59.590 --> 47:01.630 der kürzeste jetzt. 47:03.250 --> 47:07.610 Und was eben auch passieren kann, ist, wenn wir D V noch gar nicht 47:07.610 --> 47:09.110 berechnet hatten, dann ist es unendlich. 47:09.510 --> 47:12.050 Das heißt, wenn wir zum ersten Mal jetzt irgendwie an Knoten V 47:12.050 --> 47:14.810 ankommen, dann wird das auch durch diese eine Regel schon richtig 47:14.810 --> 47:15.290 gesetzt. 47:16.290 --> 47:18.930 Dann kriegen wir da auch den erstmöglichen Wert. 47:19.350 --> 47:24.350 Und was wir machen, also wenn wir einen kürzeren Pfad gefunden haben 47:24.350 --> 47:27.730 zu Knoten V, dann setzen wir eben die Distanz auch entsprechend auf 47:27.730 --> 47:31.790 diese bessere gefundenen Distanz. 47:31.910 --> 47:36.150 Also wir setzen D V auf diesen neuen Wert, der geringer ist, und 47:36.150 --> 47:40.170 updaten auch entsprechend unsere Parent-Relation, die uns dann, wenn 47:40.170 --> 47:45.690 wir sie rückwärts durchlaufen, angibt, wie wir vom Startknoten dahin 47:45.690 --> 47:45.950 kommen. 47:46.970 --> 47:49.010 Und die beiden gegebenen Intervarianten, die wir gesehen haben, 47:49.070 --> 47:50.390 bleiben natürlich erhalten. 47:53.490 --> 47:57.330 Ja, also vielleicht auch eine kleine Rennbemerkung hier noch. 47:57.950 --> 48:02.390 Dieses Update kann für einen Knoten V natürlich niemals passieren. 48:03.590 --> 48:05.630 Wir müssen uns jetzt hier natürlich nochmal ein bisschen grafisch 48:05.630 --> 48:08.370 anschauen wollen, wie das aussieht. 48:08.990 --> 48:10.810 Also wir nehmen an, wir haben hier einen Startknoten. 48:10.910 --> 48:16.870 Wir haben bisher jetzt zum Beispiel hier bis zu dem Knoten U' einen 48:16.870 --> 48:19.950 Pfad gefunden, der minimale Kosten hat. 48:20.110 --> 48:23.450 Also der läuft über U' und von dort aus dann diese Kante von U' nach 48:23.450 --> 48:23.690 V. 48:27.670 --> 48:32.090 Ja, das ist dann die Distanzwert, das hier unten, was hier 48:32.090 --> 48:32.870 angezeichnet ist. 48:33.410 --> 48:35.830 Und was wir jetzt gefunden haben, ist eben ein kürzerer Weg, der uns 48:35.830 --> 48:38.070 über U' nach V führt. 48:38.850 --> 48:43.310 Also diese Kosten hier sind geringer, was eben hier damit angedeutet 48:43.310 --> 48:45.410 ist, dass wir diese Linie weiter oben haben. 48:45.990 --> 48:49.970 Auch wenn jetzt eben hier diese Entfernung bis zum Knoten U länger 48:49.970 --> 48:51.390 ist, als bis zum Knoten U'. 48:51.390 --> 48:54.670 Aber wenn wir eben diesen einen Schritt hinzufügen, dann haben wir 48:54.670 --> 48:57.970 was, was mit geringeren Gesamtkosten oder einem kürzeren Weg zum 48:57.970 --> 48:58.650 Knoten V ist. 48:59.090 --> 49:01.990 Und dann würden wir eben das Update machen, das wir für Knoten V 49:01.990 --> 49:03.190 speichern. 49:03.630 --> 49:07.230 Der hat jetzt eben die neue Distanz dU plus cUV, hat sich verbessert 49:07.230 --> 49:08.450 im Vergleich von dem unteren. 49:08.770 --> 49:11.530 Und gleichzeitig biegen wir eben diesen Parentknoten, der uns dann 49:11.530 --> 49:16.210 nachher wirklich den kürzesten Weg angibt, um von dem bisher kürzesten 49:16.210 --> 49:19.030 Weg auf den neuen kürzesten Weg, der uns jetzt eben hierhin führt, 49:19.210 --> 49:20.070 über den Knoten U. 49:20.930 --> 49:27.450 Also bisher über den Knoten U' konnten wir von S nach V kommen. 49:27.850 --> 49:30.710 Jetzt haben wir einen kürzeren Pfad gefunden und die entsprechenden 49:30.710 --> 49:35.510 Updates sind eben dann bei der Parent-Relation und bei der Distanz. 49:38.570 --> 49:40.890 Diese Operation, die nennt sich relaxieren. 49:43.550 --> 49:45.590 Also ich bin mir nicht ganz sicher, woher der Begriff kommt. 49:45.670 --> 49:48.310 Ich finde jetzt auch nicht so sehr intuitiv, aber das ist einfach das, 49:48.490 --> 49:50.430 was ich dafür eingebürgert habe in dieser Stelle. 49:52.970 --> 49:58.290 Okay, also und damit können wir dann eigentlich schon den Algorithmus 49:58.290 --> 49:59.450 von Dijkstra formulieren. 50:01.310 --> 50:04.370 Das ist jetzt hier im ersten Schritt erstmal auf einer sehr abstrakten 50:04.370 --> 50:06.870 Ebene, ohne dass wir uns wirklich die Details anschauen, sondern nur 50:06.870 --> 50:09.310 die ganz grobe High-Level-Idee. 50:09.690 --> 50:10.350 Was machen wir? 50:10.350 --> 50:14.890 Wir initialisieren dieses Distance-Array und unser Parent-Array, so 50:14.890 --> 50:16.730 wie es auf der letzten Folie schon zu sehen war. 50:16.970 --> 50:18.350 Also eigentlich nur von den Startknoten. 50:18.450 --> 50:22.710 Für alle anderen werden die Distanzen auf unendlich gesetzt und die 50:22.710 --> 50:24.090 Parent -Knoten auf undefiniert. 50:24.510 --> 50:29.570 Und dann versuchen wir alle Knoten der Reihe nach zu scannen. 50:29.990 --> 50:33.550 Und scannen bedeutet eben, dass wir die Knoten besuchen, so wie wir 50:33.550 --> 50:35.550 das bei den anderen Zug-Algorithmen eigentlich auch schon gemacht 50:35.550 --> 50:35.850 hatten. 50:37.130 --> 50:40.550 Also markieren wir erstmal alle Knoten noch nicht gescannt. 50:41.050 --> 50:43.450 Und dann gehen wir die Knoten in der Reihe nach durch. 50:43.730 --> 50:47.410 Also solange es einen noch nicht gescannten Knoten gibt und dieser 50:47.410 --> 50:50.470 Knoten auch eine Distanz kleiner und unendlich hat. 50:51.430 --> 50:52.690 Das ist ein bisschen die technische Anforderung. 50:52.810 --> 50:54.210 Das sehen wir gleich, wozu man die braucht. 50:54.870 --> 51:04.570 Dann wählen wir den Knoten U aus, der die minimale Distanz hat. 51:06.310 --> 51:09.770 Also wählen wir den Knoten, der eben aktuell die kleinste Distanz hat. 51:10.470 --> 51:14.910 Wir wenden dann unsere Relaxation, also diese Operation, die wir auf 51:14.910 --> 51:19.690 der letzten Folie gesehen haben, auf alle von U ausgehenden Kanten an 51:19.690 --> 51:22.790 und markieren dann U als bearbeitet. 51:23.350 --> 51:25.050 Also diesen Knoten U haben wir dann gesehen. 51:25.630 --> 51:29.130 Und diese Operation, die wiederholen wir einfach in der Schleife, 51:29.230 --> 51:32.830 solange es keine weiteren nicht mehr gescannten Knoten gibt. 51:33.390 --> 51:34.230 Und dann sind wir fertig. 51:35.010 --> 51:38.430 Das ist ein sehr, sehr einfacher Algorithmus in diesen Schritten. 51:38.690 --> 51:43.010 Und was wir jetzt überlegen werden, ist warum dieser Algorithmus so 51:43.010 --> 51:43.530 funktioniert. 51:46.030 --> 51:50.870 Und was bedeutet, dass er funktioniert, bedeutet eben, dass er uns 51:50.870 --> 51:52.470 dieses kürzeste Wegeproblem löst. 51:53.430 --> 51:56.990 Also das heißt am Schluss, wenn dieser Algorithmus durchlaufen ist, 51:57.050 --> 52:01.570 soll D die optimalen Entfernungen enthalten und Parent die zugehörige 52:01.570 --> 52:08.430 Wege eben für alle Knoten den besten Weg, wie man vom Startnoten aus 52:08.430 --> 52:09.190 den erreichen kann. 52:10.730 --> 52:12.590 Aber schauen wir uns vielleicht ein Beispiel dazu an, was dieser 52:12.590 --> 52:13.290 Algorithmus macht. 52:13.570 --> 52:15.810 Also überlegen wir uns nochmal vielleicht ganz schnell, was machen 52:15.810 --> 52:15.950 wir. 52:16.070 --> 52:19.530 Wir suchen uns einfach den Knoten mit der aktuell geringsten Distanz 52:19.530 --> 52:24.010 aus und bearbeiten dann diesen Knoten, indem wir einfach uns alle 52:24.010 --> 52:29.450 Kanten anschauen und dann eben die, wenn wir die Fläche weiter 52:29.450 --> 52:32.490 durchlaufen, praktisch die Kante wieder mit dem geringsten, mit der 52:32.490 --> 52:34.250 aktuell geringsten Distanz dann weiterlaufen. 52:36.710 --> 52:38.070 Also was sehen wir hier oben? 52:38.150 --> 52:41.930 Das ist unser Startgraph und S ist unser Startknoten hier. 52:42.510 --> 52:44.750 Und Sie sehen, die Kanten sind jetzt hier auch schon mit Gewichten 52:44.750 --> 52:46.450 oder mit Kosten verknüpft. 52:46.530 --> 52:50.370 Das heißt, um von S nach A zu kommen, müssen wir zum Beispiel 2 zu 52:50.370 --> 52:52.950 unseren Kosten zuschlagen oder unsere Distanz. 52:53.970 --> 52:56.310 Und hier zum Beispiel nach D hätten wir eine Distanz von 10. 52:57.010 --> 53:00.330 Am Anfang haben wir nur den Knoten S markiert, der hat die Distanz 0, 53:00.490 --> 53:02.150 also den Knoten, den wir auswählen müssen. 53:02.470 --> 53:05.310 Alle anderen haben anfangs die Distanz unendlich, also müssen wir den 53:05.310 --> 53:10.350 Startknoten auswählen und von dem Knoten jetzt ausgehend einfach die 53:10.350 --> 53:13.370 Distanzen setzen für alle nachfolgenden Knoten. 53:14.710 --> 53:18.310 Also und das eben mit Hilfe dieser Relax-Operation. 53:18.670 --> 53:22.430 Also wir wissen hier, Startknoten S hat Distanz 0 von sich selber, 53:23.010 --> 53:25.810 alle nachfolgenden Knoten, das sind eben einmal der Knoten A und der 53:25.810 --> 53:26.390 Knoten D. 53:27.450 --> 53:31.310 Hier haben wir Kosten 2, dann wissen wir aktuell, wenn hier 0 ist und 53:31.310 --> 53:35.950 hier 2 dazukommen, hat dieser Knoten hier auch eine Distanz von 2 vom 53:35.950 --> 53:36.610 Startknoten. 53:37.430 --> 53:39.970 Und hier unten würden wir herausfinden, ja hier kommt 10 dazu, also 53:39.970 --> 53:43.890 hat dieser Knoten D aktuell die Distanz 10 vom Startknoten. 53:45.010 --> 53:47.690 Und das sind jetzt einfach von dem, was wir bisher gesehen haben, die 53:47.690 --> 53:49.610 aktuell besten Werte. 53:50.470 --> 53:53.550 Und man wird jetzt gleichzeitig dann eben diese Parent-Kanten 53:53.550 --> 53:54.330 eintragen. 53:55.190 --> 53:58.090 Was man dann macht, ist im nächsten Schritt, wir wählen jetzt von 53:58.090 --> 54:02.150 diesen beiden Nachfolgern denjenigen mit geringstem Gewicht aus. 54:02.490 --> 54:05.310 Also wir schauen, was ist der mit geringstem Gewicht, das ist hier die 54:05.310 --> 54:05.590 2. 54:06.350 --> 54:08.370 Also arbeiten wir hier oben mit der 2 weiter. 54:09.070 --> 54:11.810 Und da wieder überholen wir einfach den Algorithmus jetzt weiter. 54:11.910 --> 54:13.250 Wir schauen dann, was sind die Nachfolger. 54:13.830 --> 54:15.790 Wir wählen dann den mit geringstem Gewicht, den wir nachher wieder 54:15.790 --> 54:16.270 auswählen. 54:16.610 --> 54:19.890 Hier haben wir aber nur einen Nachfolger mit Distanz 3, also bekommt 54:19.890 --> 54:21.670 Knoten B die Distanz 5. 54:21.910 --> 54:25.910 Wir wählen eben zu der bisher geringsten Distanz 2, die 3 noch 54:25.910 --> 54:27.510 dazukommen, also sind wir bei 5. 54:28.510 --> 54:30.270 Gut, dann wird der hier entsprechend markiert. 54:30.710 --> 54:33.490 Und auch diese Parent-Kante hier praktisch wieder eingezeichnet. 54:33.650 --> 54:37.410 Also der kürzeste Weg jetzt, um zu Knoten B zu kommen, wäre eben jetzt 54:37.410 --> 54:41.750 der, der über A von S nach B führt. 54:43.170 --> 54:46.850 Dann gehen wir hier wieder weiter, schauen uns an, explorieren oder 54:46.850 --> 54:53.910 betrachten die Nachfolgeknoten hier, oder relaxieren die. 54:54.450 --> 55:01.850 Das wären dann diese Knoten 2, die Knoten C, der Knoten E und mehr 55:01.850 --> 55:02.670 gibt es hier auch nicht. 55:04.250 --> 55:08.050 Also hier kommt 1 dazu, also hat dieser Knoten hier unten die Distanz 55:08.050 --> 55:08.630 6. 55:09.170 --> 55:10.830 Dieser obere Knoten hat Distanz 7. 55:11.430 --> 55:16.170 Dann wählen wir wieder den Knoten mit der geringsten Distanz aus, also 55:16.170 --> 55:17.230 das ist hier der Knoten 6. 55:17.570 --> 55:19.070 Dann gehen wir von hier aus weiter. 55:19.190 --> 55:23.210 Hier gibt es einerseits die Kante nach 9, aber die interessiert uns 55:23.210 --> 55:26.530 nicht, weil dieser Knoten bereits markiert ist. 55:26.630 --> 55:30.590 Und hier dann diese Kante mit Gewicht 0. 55:32.810 --> 55:36.550 Und die gehen wir dann weiter und können dann auch diesem Knoten hier 55:36.550 --> 55:37.750 eine Distanz zuordnen. 55:38.890 --> 55:42.530 Sie sehen, also hier tritt jetzt dann wirklich dieser Effekt ein, dass 55:42.530 --> 55:46.170 wir eine schon zuvor berechnete Distanz, nämlich da hatten wir bisher 55:46.170 --> 55:51.670 10, wird jetzt zu 6 dann abgeändert hier, weil wir eben über diesen 55:51.670 --> 55:55.570 Umweg hier außen rum schneller ans Ziel kommen, als wenn wir diese 55:55.570 --> 55:57.570 eine Kante mit Gewicht 10 laufen würden. 55:58.750 --> 56:05.550 Also hier der äußere Weg hat 2 plus 3 plus 1 plus 0, also 6 als Kosten 56:05.550 --> 56:08.810 oder als Distanz, während der direkte Weg hier eben 10 hätte. 56:10.430 --> 56:13.150 Jetzt haben wir diesen kürzen Pfad gefunden, der wird dann auch eben 56:13.150 --> 56:16.770 entsprechend über diese Apparent-Kanten gemerkt. 56:18.010 --> 56:21.770 Dann sind wir damit fertig, haben den nächsten Knoten mit geringstem 56:21.770 --> 56:27.570 Gewicht, hier ist die 7, schauen uns den an und haben von dem dann 56:27.570 --> 56:29.530 eben auch die Distanz eingetragen. 56:29.810 --> 56:34.790 Es gibt keine weiteren nachvollziehbaren Knoten und wir haben alle 56:34.790 --> 56:37.770 Knoten markiert, bis auf den hier unten. 56:39.130 --> 56:42.390 Und woran liegt es, dass dieser Knoten hier unten nicht gefunden 56:42.390 --> 56:42.670 wurde? 56:42.750 --> 56:47.230 Der ist eben nicht erreichbar vom Startknoten aus und nachdem der 56:47.230 --> 56:51.690 ursprünglich mit Distanz unendlich markiert worden ist, werden wir den 56:51.690 --> 56:55.050 auch in unserer Schleife nicht weiter berücksichtigen, sondern dieser 56:55.050 --> 56:58.510 kürzte -Weg-Algorithmus ist damit abgeschlossen und das heißt, dieser 56:58.510 --> 57:02.570 Knoten behält damit weiterhin seine Distanz unendlich, weil er eben 57:02.570 --> 57:04.490 nicht erreichbar ist vom Startknoten aus. 57:07.310 --> 57:10.630 Okay, also so arbeitet der Algorithmus an diesem Beispiel. 57:12.390 --> 57:14.830 Jetzt überlegen wir uns kurz die Korrektheit und dann schauen wir uns 57:14.830 --> 57:17.390 noch ein bisschen an, wie man das jetzt im Detail implementiert. 57:20.630 --> 57:23.970 Also, die Korrektheit wollen wir in zwei Schritten zeigen. 57:25.310 --> 57:30.370 Der erste Schritt soll erstmal sein, dass ein erreichbarer Knoten 57:30.370 --> 57:31.390 überhaupt betrachtet wird. 57:31.830 --> 57:35.890 Also ist es so, dass wenn ein Knoten eben vom Startknoten aus über 57:35.890 --> 57:38.790 irgendwelche Pfade erreicht werden kann, dass es dann irgendwann 57:38.790 --> 57:43.310 betrachtet oder gescannt wird von diesem Algorithmus, also dass wir 57:43.310 --> 57:46.070 überhaupt die Möglichkeit haben, einen kürzesten Pfad zu finden. 57:47.050 --> 57:50.210 Und dann der zweite Schritt in unserem Korrektheitsbeweis, der soll 57:50.210 --> 57:54.990 eben dann diese Optimalitätsbedingungen garantieren und das bedeutet, 57:55.350 --> 58:00.070 wenn der Knoten gescannt wird, dann soll eben diese Distanz nach 58:00.070 --> 58:05.190 Ablauf des Algorithmus auch das Minimum sein, diese minimal mögliche 58:05.190 --> 58:06.510 Distanz vom Startknoten aus. 58:08.810 --> 58:13.530 Okay, also in den beiden Teilen wollen wir uns jetzt die Korrektheit 58:13.530 --> 58:13.990 anschauen. 58:16.490 --> 58:19.010 Und das erste ist die Erreichbarkeit. 58:20.170 --> 58:24.510 Und die Aussage steht oben auf der Folie, was wir zeigen wollen, dass 58:24.510 --> 58:28.110 wenn der Knoten V erreichbar ist, dass er dann auch irgendwann 58:28.110 --> 58:30.550 gescannt wird, also dass der Algorithmus den nicht übersieht. 58:32.870 --> 58:36.390 Also nehmen wir mal an, dass das Gegenteil der Fall wäre und was wir 58:36.390 --> 58:39.250 dann machen, versuchen einen Widerspruch zu machen. 58:39.730 --> 58:42.350 Wir nehmen das Gegenteil an und versuchen zu zeigen, dass da ein 58:42.350 --> 58:44.030 Widerspruch dann daraus entsteht. 58:45.170 --> 58:50.050 Also unsere gegenteilige Annahme ist, V ist erreichbar, aber wird 58:50.050 --> 58:51.190 nicht gescannt. 58:52.350 --> 58:53.910 Und genau was bedeutet das denn? 58:54.010 --> 58:59.370 Also wir haben hier unser gedachtes Ergebnis, also den kürzesten Pfad 58:59.370 --> 59:02.950 von S nach V und was dann passieren muss, wenn er nicht gescannt wird, 59:03.010 --> 59:05.390 dann muss es eben irgendeinen Knoten geben, also entweder ein 59:05.390 --> 59:08.830 Zielknoten oder einen, der vorher schon auf diesem Pfad liegt, der 59:08.830 --> 59:09.770 nicht gescannt wurde. 59:12.090 --> 59:17.910 Genau und dann wäre zwar, wenn wir eben diese Kette hier haben, über 59:17.910 --> 59:21.490 Kanten, wäre der Knoten erreichbar V, aber er würde eben nicht 59:21.490 --> 59:22.230 gescannt werden. 59:23.870 --> 59:26.510 Und jetzt nehmen wir an, dass wir hier irgendeinen Punkt haben, bis 59:26.510 --> 59:30.230 wohin das Ganze gescannt wird und dann eben zum ersten Mal ein Knoten 59:30.230 --> 59:31.470 nicht mehr gescannt wird. 59:32.670 --> 59:35.810 Okay, also V i minus 1, der soll noch vom Algorithmus erkannt werden, 59:35.950 --> 59:38.570 aber der nächste Knoten dann nicht mehr und den muss es ja geben, weil 59:38.570 --> 59:43.250 nach unserer Annahme eben der Zielknoten nicht gescannt wird. 59:43.870 --> 59:48.030 Also der Knoten V i minus 1 wird noch gescannt und wenn dieser Knoten 59:48.030 --> 59:51.590 gescannt wird, dann wissen wir auch, dass unser Algorithmus dann eben 59:51.590 --> 59:57.270 für alle Nachfolgekanten die relaxiert. 59:57.530 --> 01:00:02.510 Also diese Kanten hier betrachtet, die von dem V i minus 1 eben einen 01:00:02.510 --> 01:00:03.290 Schritt weiter gehen. 01:00:04.370 --> 01:00:09.710 Also das wird relaxiert und daraus folgt, dass dieser Knoten V i dann 01:00:09.710 --> 01:00:12.430 auch eine Distanz zugeordnet bekommt. 01:00:12.590 --> 01:00:15.910 Das war ja Teil dieses Relaxierens und die Distanzen, die zugeordnet 01:00:15.910 --> 01:00:18.230 werden, sind natürlich dann immer unterschiedlich von diesem 01:00:18.230 --> 01:00:18.690 Unendlich. 01:00:18.750 --> 01:00:21.410 Das wird ja nur einmal bei der Initialisierung gesetzt, solange sie 01:00:21.410 --> 01:00:22.470 noch nicht gescannt wurden. 01:00:23.070 --> 01:00:26.370 Das heißt, wir haben dann für diesen Knoten eine Distanz, die kleiner 01:00:26.370 --> 01:00:27.310 als unendlich ist. 01:00:30.250 --> 01:00:35.190 Und wenn man sich dann anschaut, wenn wir hier eine Distanz kleiner 01:00:35.190 --> 01:00:37.310 als unendlich haben, dann ist es ein Widerspruch zu unserem 01:00:37.310 --> 01:00:42.650 Algorithmus, der ja sich alle Knoten betrachtet, die irgendeine 01:00:42.650 --> 01:00:46.090 Distanz zugeordnet haben, die nicht unendlich ist. 01:00:46.550 --> 01:00:47.990 Also schauen wir uns mal kurz hier zurück. 01:00:49.130 --> 01:00:53.990 Hier hatten wir alle nicht gescannten Knoten mit Distanz kleiner als 01:00:53.990 --> 01:00:55.690 unendlich werden hier betrachtet. 01:00:55.870 --> 01:00:58.330 Und solange es noch welche gibt, arbeitet der Algorithmus auch weiter. 01:00:58.490 --> 01:01:03.150 Das heißt, wenn es hier dieser Knoten mit Distanz kleiner als 01:01:03.150 --> 01:01:05.350 unendlich hat, wird er irgendwann mal auch hier betrachtet werden. 01:01:07.430 --> 01:01:14.370 Also hätten wir hier jetzt einen Widerspruch, dass wenn wir wissen, 01:01:14.590 --> 01:01:19.350 dass nur Knoten mit Distanz unendlich nicht gescannt werden, aber 01:01:19.350 --> 01:01:22.970 dieser Knoten hier jetzt eben gescannt wurde, also Widerspruch. 01:01:23.470 --> 01:01:27.130 Deshalb muss unsere Annahme falsch gewesen sein. 01:01:27.450 --> 01:01:29.990 Also ist es nicht möglich, dass ein Knoten erreichbar ist und nicht 01:01:29.990 --> 01:01:30.670 gescannt wird. 01:01:31.330 --> 01:01:34.930 Und deshalb wissen wir eben, dass alle erreichbaren Knoten dann 01:01:34.930 --> 01:01:36.050 wirklich gescannt werden. 01:01:37.790 --> 01:01:38.710 Gut, das ist schon mal schön. 01:01:38.950 --> 01:01:43.110 Das heißt, wir finden schon mal zumindest irgendeinen Pfad zu jedem 01:01:43.110 --> 01:01:45.910 Knoten, der vom Start aus erreichbar ist. 01:01:49.890 --> 01:01:52.290 Dann wenden wir uns jetzt gleich der Optimalität zu, aber es gibt noch 01:01:52.290 --> 01:01:53.830 einen kleinen Spezialfall. 01:01:54.870 --> 01:01:59.030 Und zwar, was ist, wenn wir hier den Fall i gleich 1 haben? 01:01:59.970 --> 01:02:12.500 Also das heißt, wenn der Startknoten selber nicht gescannt wäre, aber 01:02:12.500 --> 01:02:16.320 das kann natürlich auch nicht sein, weil der Startknoten wird ja nach 01:02:16.320 --> 01:02:18.980 der Initialisierung direkt gescannt. 01:02:19.100 --> 01:02:22.500 Er ist ja der einzige Knoten, der eine Distanz unendlich hat. 01:02:22.860 --> 01:02:25.560 Muss deshalb von dem Scan-Algorithmus betrachtet werden, also kann 01:02:25.560 --> 01:02:26.880 auch dieser Fall nicht eintreten. 01:02:27.760 --> 01:02:29.100 Also wie gesagt, ein kleiner Randfall noch. 01:02:31.920 --> 01:02:34.120 Dann betrachten wir jetzt diesen zweiten Teil. 01:02:34.840 --> 01:02:38.280 Also wir wissen, alle erreichbaren Knoten werden gescannt. 01:02:38.740 --> 01:02:42.280 Jetzt also die Frage, wenn der Knoten gescannt wurde, ist dann danach 01:02:42.280 --> 01:02:44.220 das Ergebnis auch wirklich das Optimum? 01:02:44.860 --> 01:02:45.980 Ist das der kürzeste Weg? 01:02:48.560 --> 01:02:52.480 Also und Optimum bedeutet eben, dass unser DEV, was wir berechnet 01:02:52.480 --> 01:02:56.400 haben, gleich dem theoretisch minimal möglichen ist. 01:02:57.240 --> 01:03:00.080 Und jetzt wollen wir auch wieder hier einen Widerspruchsbeweis machen, 01:03:00.380 --> 01:03:02.400 oder zumindest die Idee eines Widerspruchsbeweises möchte ich Ihnen 01:03:02.400 --> 01:03:02.960 präsentieren. 01:03:03.420 --> 01:03:06.520 Und deshalb nehmen wir auch hier wieder das Gegenteil an, also V wurde 01:03:06.520 --> 01:03:11.920 gescannt, aber die am Schluss berechnete Distanz ist eben nicht das 01:03:11.920 --> 01:03:12.460 Optimum. 01:03:12.460 --> 01:03:18.480 Also die Distanz ist größer als das theoretisch mögliche Optimum hier, 01:03:18.680 --> 01:03:19.220 der kleinste. 01:03:20.820 --> 01:03:25.020 Okay, also das nehmen wir mal an, dass unsere berechnete Distanz eben 01:03:25.020 --> 01:03:26.360 größer ist als Optimum. 01:03:29.200 --> 01:03:35.260 Gut, jetzt betrachten wir einfach oder nehmen an, dass dieses V hier 01:03:35.260 --> 01:03:39.980 der erste gescannte Knoten ist, wo es der Fall ist, dass die Distanz 01:03:39.980 --> 01:03:41.420 praktisch falsch berechnet wird. 01:03:43.700 --> 01:03:48.700 Also das heißt, wir können ja einfach auf dieser Kette, wo diese 01:03:48.700 --> 01:03:51.820 Fehlberechnung stattfindet, einfach uns immer den ersten aussuchen, 01:03:51.940 --> 01:03:57.420 der eben während der im Algorithmenlauf der erste war, der mit so 01:03:57.420 --> 01:03:59.660 einem fehlerhaften Ergebnis generiert wurde. 01:04:00.200 --> 01:04:04.360 Das reicht natürlich aus, wenn wir nur den betrachten und nicht 01:04:04.360 --> 01:04:05.240 irgendwelche beliebigen. 01:04:06.160 --> 01:04:09.100 Gut, dann nehmen wir an, also auch hier wieder den Pfad, der uns eben 01:04:09.100 --> 01:04:11.460 von dem Startknoten zu einem Knoten V führt. 01:04:11.980 --> 01:04:15.520 Jetzt dann eben mit dieser nicht einschränkenden Zusatzannahme, dass 01:04:15.520 --> 01:04:19.820 die Scansate so ist, dass wir hier einen Startblock haben, wo die 01:04:19.820 --> 01:04:24.780 Scansate vor dem Scannen unseres Zielknotens V liegt. 01:04:25.040 --> 01:04:27.260 Und dann gibt es eben eine Reihe von anderen Knoten, die danach 01:04:27.260 --> 01:04:28.020 gescannt wurden. 01:04:28.400 --> 01:04:31.460 Aber die danach gescannten Knoten, die haben nicht dazu geführt, dass 01:04:31.460 --> 01:04:35.380 eben sich dieses Ergebnis hier irgendwie noch modifiziert hat, sondern 01:04:35.380 --> 01:04:37.400 das ist eben auf dem alten Wert geblieben. 01:04:39.880 --> 01:04:43.960 Wobei wir ja jetzt annehmen, dass das irgendwie der falsche wäre, der 01:04:43.960 --> 01:04:45.400 eben nicht das Optimum darstellt. 01:04:47.360 --> 01:04:49.100 Gut, was haben wir dann zu der Zeit T? 01:04:49.320 --> 01:04:55.320 Also die Zeit, in der wir diesen Knoten V zum ersten Mal praktisch 01:04:55.320 --> 01:04:56.260 gesehen haben. 01:04:57.160 --> 01:05:02.500 Da war das so, dass für den Vorgängerknoten auf jeden Fall noch die 01:05:02.500 --> 01:05:03.900 Optimalitätseigenschaft gilt. 01:05:04.160 --> 01:05:06.720 Das ist ja unsere Annahme, dass das praktisch der erste ist, wo das 01:05:06.720 --> 01:05:07.180 nicht gilt. 01:05:07.740 --> 01:05:13.240 Also wissen wir, für den Knoten V i minus 1 gilt noch diese 01:05:13.240 --> 01:05:17.260 Optimalitätsbedingung, dass der berechnete Wert wirklich der richtige 01:05:17.260 --> 01:05:17.600 ist. 01:05:19.660 --> 01:05:21.220 Was hat der Algorithmus dann gemacht? 01:05:21.360 --> 01:05:26.800 In dem Algorithmus wurde dann diese Kante V i minus 1 nach V i 01:05:26.800 --> 01:05:30.700 relaxiert, weil ja das eben der nächste Knoten war, der betrachtet 01:05:30.700 --> 01:05:31.080 wurde. 01:05:32.760 --> 01:05:37.580 Und daraus folgt dann diese Ungleichungskette, die wir jetzt hier mal 01:05:37.580 --> 01:05:39.100 Schritt für Schritt betrachten wollen. 01:05:39.700 --> 01:05:44.000 Also diese Distanz, die dann für den Knoten V i gilt, ist auf jeden 01:05:44.000 --> 01:05:49.440 Fall so, das ist ja die Definition von der Relaxation, dass die 01:05:49.440 --> 01:05:52.500 MLSchlussberechnete muss auf jeden Fall kleiner gleich sein als das, 01:05:52.600 --> 01:05:55.800 was jetzt in diesem Schritt sich eben als Distanz ergeben hatte, also 01:05:55.800 --> 01:05:56.520 in Zeit Schritt T. 01:05:57.120 --> 01:06:02.420 Das wäre dass man diese optimale Distanz bereits hatte, plus die 01:06:02.420 --> 01:06:05.820 letzte Kante, die noch dazukommt für den nächsten Schritt, um den 01:06:05.820 --> 01:06:07.020 Knoten V i zu erreichen. 01:06:08.780 --> 01:06:17.660 Das ist dann gleichzeitig das Optimum von den Knoten V i und das ist 01:06:17.660 --> 01:06:24.160 kleiner gleich als das, was wir von den Knoten V als Optimum berechnet 01:06:24.160 --> 01:06:28.840 haben, weil da ja noch weitere Kanten hier dazukommen, zumindest das 01:06:28.840 --> 01:06:29.600 nicht davor liegt. 01:06:30.460 --> 01:06:33.880 Und dann war unsere Annahme hier oben, dass das eben nicht optimal 01:06:33.880 --> 01:06:38.360 ist, also deshalb ist µ von V kleiner als d von V ist. 01:06:41.940 --> 01:06:46.100 Gut, wenn aber jetzt das so wäre, wie wir jetzt gerade eben abgelehnt 01:06:46.100 --> 01:06:50.160 haben, dass das d von V i, also die Distanz von V i, kleiner als die 01:06:50.160 --> 01:06:55.780 Distanz von V ist, dann hätte unser Algorithmus ja immer den kleinsten 01:06:55.780 --> 01:07:01.040 Wert der Distanz zum Fortsitzen wählt, hätte er an dieser Stelle, hier 01:07:01.040 --> 01:07:04.620 zum Zeitpunkt T, nicht den Knoten V wählen dürfen, sondern hätte den 01:07:04.620 --> 01:07:08.960 Knoten V i wählen müssen, wenn er einen echt kleineren Wert hat als 01:07:08.960 --> 01:07:11.920 der Knoten, eine kleinere Distanz als dV. 01:07:12.840 --> 01:07:15.600 Das hat unser Algorithmus aber nicht gemacht, also kann diese 01:07:15.600 --> 01:07:18.760 Situation, wie wir sie hier oben uns jetzt dargestellt haben, nicht 01:07:18.760 --> 01:07:19.760 aufgetreten sein. 01:07:20.680 --> 01:07:23.620 Und wir haben damit auch wieder einen Widerspruch zu der Annahme, dass 01:07:23.620 --> 01:07:26.120 eben dieses berechnete Optimum nicht optimal ist. 01:07:29.460 --> 01:07:29.640 Okay, 01:07:33.380 --> 01:07:37.880 also hier mit zwei Widerspruchsbeweisen können wir zeigen, dass der 01:07:37.880 --> 01:07:41.820 Algorithmus korrekt arbeitet, dass er wirklich alle Knoten markiert, 01:07:41.880 --> 01:07:44.240 die erreichbar sind und dass er für diese Knoten auch die minimale 01:07:44.240 --> 01:07:45.060 Distanz findet. 01:07:46.840 --> 01:07:51.440 Ein bisschen sind solche Widerspruchsbeweise manchmal oder häufig 01:07:51.440 --> 01:07:54.420 wenig intuitiv, dass sie einem wenig irgendwie auf den Grund hin 01:07:54.420 --> 01:07:56.380 steuern, warum das jetzt so ist dann. 01:07:56.840 --> 01:08:00.280 Aber ich denke, im Grunde ist der Algorithmus selber für sich genommen 01:08:00.280 --> 01:08:05.480 auch so, dass er plausibel wirkt, dass man damit einen kürzen Weg 01:08:05.480 --> 01:08:06.000 finden kann. 01:08:06.500 --> 01:08:12.280 Und hier eben dann jetzt noch die formalen Beweise dann, mit denen man 01:08:12.280 --> 01:08:13.380 sowas nachweisen könnte. 01:08:19.010 --> 01:08:21.750 Okay, überlegen wir uns noch ein bisschen was in der letzten 01:08:21.750 --> 01:08:23.150 Viertelstunde zur Implementierung. 01:08:23.910 --> 01:08:25.930 Also was ist der Hauptschritt in diesem Algorithmus? 01:08:26.830 --> 01:08:30.250 Eigentlich ist dieser Hauptschritt hier dieses Finden von 01:08:30.250 --> 01:08:36.650 Nachfolgeknoten oder Finden eines Knotens mit minimalem Wert dv. 01:08:37.810 --> 01:08:44.350 Also wir müssen irgendwo in unserem Graph den Knoten finden, der eine 01:08:44.350 --> 01:08:46.470 minimale Distanz dv aufweist. 01:08:46.750 --> 01:08:49.590 Mit dem wollen wir ja wieder fortsetzen und dort auf diesem Knoten 01:08:49.590 --> 01:08:54.310 dann diese Expansion oder diese Relaxation dann durchführen. 01:08:55.330 --> 01:09:01.630 Also wie können wir das Minimum finden in einer gegebenen Menge? 01:09:01.990 --> 01:09:04.010 Also wir haben eine Knotenmenge gegeben und wollen da das Minimum 01:09:04.010 --> 01:09:04.830 schnell finden können. 01:09:06.570 --> 01:09:09.770 Und wenn man sich zurückerinnert, wir hatten ja so eine Datenstruktur, 01:09:09.890 --> 01:09:14.130 die uns erlaubt für Sequenzen Minimum schnell zu identifizieren. 01:09:15.070 --> 01:09:18.950 Und das waren diese Prioritätslisten oder die Priority Queues. 01:09:19.970 --> 01:09:24.450 Also die bieten uns genau die Möglichkeit, ein minimales Element aus 01:09:24.450 --> 01:09:27.190 einer gegebenen Menge schnell zu identifizieren. 01:09:28.570 --> 01:09:31.230 Und deshalb wollen wir auch hier Prioritätslisten einsetzen. 01:09:33.670 --> 01:09:39.190 Und das bedeutet, also das was unser Minimum ist, das wir suchen 01:09:39.190 --> 01:09:44.010 wollen, ist ja immer unsere Distanz für alle Knoten. 01:09:45.370 --> 01:09:48.630 Das heißt, das wird dann auch der Schlüssel sein, nachdem wir in der 01:09:48.630 --> 01:09:51.750 Prioritätsliste eben sortieren oder auf dem basieren wir das Minimum 01:09:51.750 --> 01:09:52.350 immer suchen. 01:09:54.030 --> 01:09:58.350 Und was wir in unserer Prioritätsliste speichern, sind eben die 01:09:58.350 --> 01:09:58.830 Knoten. 01:09:59.070 --> 01:10:02.610 Und nicht alle Knoten, sondern die Knoten, die noch betrachtet werden 01:10:02.610 --> 01:10:02.910 müssen. 01:10:03.470 --> 01:10:08.010 Das heißt, die ungescannten erreichten Knoten. 01:10:08.150 --> 01:10:12.550 Also das, was in diesem Algorithmus eben an der entsprechend rot 01:10:12.550 --> 01:10:15.750 markierten oder rot eingerendeten Stelle zu sehen war. 01:10:17.430 --> 01:10:20.730 Also diese Knoten, die wollen wir in einer Prioritätsliste speichern. 01:10:22.290 --> 01:10:26.570 Und diese Prioritätsliste, das soll auch eine adressierbare 01:10:26.570 --> 01:10:28.110 Prioritätsliste sein. 01:10:29.410 --> 01:10:31.830 Sollen wir uns auch nochmal zurückerinnern, was war denn die 01:10:31.830 --> 01:10:32.690 Adressierbarkeit? 01:10:32.830 --> 01:10:34.150 Was hat uns die erlaubt? 01:10:35.970 --> 01:10:38.750 Also Prioritätsliste war erstmal, sagen wir mal, die Hauptoperation 01:10:38.750 --> 01:10:41.710 war Minimum finden in der Liste. 01:10:42.230 --> 01:10:45.270 Und adressierbar hat dann eben bestimmte Updates noch ermöglicht. 01:10:45.430 --> 01:10:50.490 Also zum Beispiel Elemente zu entfernen, einzufügen oder ein Update zu 01:10:50.490 --> 01:10:56.490 machen des Gewichts oder dieser Priorität, die eben einem bestimmten 01:10:56.490 --> 01:10:57.670 Element zugeordnet wird. 01:10:58.570 --> 01:11:00.770 Also das ist das, was wir hier unter adressierbar haben. 01:11:01.550 --> 01:11:04.690 Und diese Eigenschaft brauchen wir auch deswegen, weil wir eben auch 01:11:04.690 --> 01:11:10.610 hier unsere Schlüssel, die Distanzen immer wieder aktualisieren müssen 01:11:10.610 --> 01:11:11.090 zwischendrin. 01:11:11.350 --> 01:11:14.390 Also wenn wir einen kürzeren Weg gefunden haben, müssen wir dieses DV 01:11:14.390 --> 01:11:18.270 immer wieder neu aktualisieren und deshalb eben diese zusätzlichen 01:11:18.270 --> 01:11:23.350 Operationen auf Prioritätslisten, die uns eben diese adressierbaren 01:11:23.350 --> 01:11:24.750 Prioritätslisten erlaubt haben. 01:11:27.550 --> 01:11:30.330 Genau, und das war jetzt wieder dieser technische Aspekt. 01:11:31.370 --> 01:11:35.170 Wenn wir das adressierbar halten wollen, dann hatten wir praktisch 01:11:35.170 --> 01:11:41.750 immer Pointer auf Elemente in unserer Prioritätsliste, die eben 01:11:41.750 --> 01:11:44.110 Handles genannt wurden. 01:11:44.250 --> 01:11:47.050 Also Referenzen oder Zeiger, die mit einzelnen Elementen ansprechen 01:11:47.050 --> 01:11:47.390 können. 01:11:52.800 --> 01:11:54.840 Okay, also Prioritätsliste wollen wir einführen. 01:11:56.780 --> 01:12:03.100 Und gut, wenn wir uns das jetzt anschauen, jetzt haben wir eigentlich 01:12:03.100 --> 01:12:06.520 schon alle Zutaten zusammen, die man braucht, um den Dijkstra 01:12:06.880 --> 01:12:08.000 Algorithmus zu beschreiben. 01:12:09.640 --> 01:12:12.400 Und so ganz grob kann man sich das vorstellen. 01:12:12.500 --> 01:12:13.140 Was ist Dijkstra? 01:12:13.580 --> 01:12:18.140 Eigentlich nicht viel anders als eine Breitensuche mit Priority-Queues 01:12:18.140 --> 01:12:22.620 anstelle einer normalen Queue, also einer FIFO-Datenstruktur. 01:12:24.360 --> 01:12:26.600 Also deshalb sieht der Algorithmus auch dann noch ein bisschen ähnlich 01:12:26.600 --> 01:12:27.200 aus wieder. 01:12:27.680 --> 01:12:32.060 Also wir haben eine Funktion Dijkstra mit einem Startnoten gegeben. 01:12:32.400 --> 01:12:39.040 Der Graph, der ist irgendwo in der Klasse enthalten, wo diese Funktion 01:12:39.040 --> 01:12:39.680 dazugehört. 01:12:39.800 --> 01:12:41.960 Das heißt, der wird hier nicht explizit als Argument übergeben. 01:12:42.500 --> 01:12:43.400 Und was berechnet er? 01:12:45.060 --> 01:12:47.520 Zwei Arrays bekommen wir als Ausgabe. 01:12:47.660 --> 01:12:51.020 Einerseits eben diese Distanzrelation für jeden Knoten und 01:12:51.020 --> 01:12:55.100 andererseits diese Parent-Relation für jeden Knoten. 01:12:55.360 --> 01:12:59.240 Also die Kante, die uns wieder Richtung Startnoten führt und uns eben 01:12:59.240 --> 01:13:02.020 anzeigt, was denn jetzt genau der kürzeste Pfad ist. 01:13:02.840 --> 01:13:04.540 Dann die Initialisierung hatten wir eigentlich auch schon 01:13:04.540 --> 01:13:05.100 angesprochen. 01:13:05.240 --> 01:13:08.060 Die läuft so ab, dass wir eben alle Distanzen erstmal auf unendlich 01:13:08.060 --> 01:13:12.580 setzen und die Parent-Knoten alle auf undefiniert setzen. 01:13:13.380 --> 01:13:15.580 Dann initialisieren wir noch den Startknoten. 01:13:16.180 --> 01:13:17.880 Da haben wir gesagt, Parent ist der Knoten selber. 01:13:18.400 --> 01:13:22.280 Das heißt, wir haben da diese Loop, die auf den Knoten selber geht. 01:13:23.100 --> 01:13:31.340 Dann die Priority Queue müssen wir initialisieren mit den noch nicht 01:13:31.340 --> 01:13:35.380 gescannten erreichbaren Knoten. 01:13:35.740 --> 01:13:38.520 Aber die soll anfangs erstmal leer sein und wird hier praktisch nur 01:13:38.520 --> 01:13:40.760 auf eine leere Queue initialisiert. 01:13:41.240 --> 01:13:44.700 Dann setzen wir die Distanz von den Startknoten und fügen den 01:13:44.700 --> 01:13:45.940 Startknoten auch in die Queue ein. 01:13:46.740 --> 01:13:50.800 Damit haben wir dann unsere Initialisierung soweit abgeschlossen. 01:13:51.460 --> 01:13:53.300 Also Startknoten ist eingetragen. 01:13:54.280 --> 01:13:58.600 Wir haben die anderen Knoten alle auf undefiniert bzw. 01:13:58.780 --> 01:14:02.620 unendlich gesetzt und können jetzt mit dem eigentlichen Algorithmus 01:14:02.620 --> 01:14:02.980 beginnen. 01:14:06.060 --> 01:14:08.360 Was macht der Algorithmus? 01:14:08.360 --> 01:14:10.120 Also hier nochmal kurz die Initialisierung. 01:14:10.260 --> 01:14:12.200 Das ist jetzt hier auf der obersten Seite zusammengefasst. 01:14:12.320 --> 01:14:15.700 Wir haben in diese Queue unseren Startknoten, unsere Priority Queue 01:14:15.700 --> 01:14:18.720 den Startknoten initialisiert und gehen jetzt einfach die Queue so 01:14:18.720 --> 01:14:22.940 lange durch, solange sie noch nicht leer ist. 01:14:24.560 --> 01:14:28.280 Also solange wir noch Elemente haben, die wir bearbeiten müssen, gehen 01:14:28.280 --> 01:14:31.960 wir so vor, wie wir sie auch vorher in dem Beispiel gesehen haben oder 01:14:31.960 --> 01:14:33.380 in dem etwas abstrakteren Algorithmus. 01:14:33.720 --> 01:14:39.960 Wir suchen uns dasjenige Element mit U aus, also den Knoten, der die 01:14:39.960 --> 01:14:43.260 kleinste Distanz aktuell hat. 01:14:44.480 --> 01:14:47.960 Das entspricht unserer Operation DELETE MIN auf Priority Queues. 01:14:48.540 --> 01:14:51.940 Wir suchen das kleinste Element, löschen das aus der Queue raus und 01:14:51.940 --> 01:14:52.680 geben das zurück. 01:14:52.960 --> 01:14:53.660 Das ist unsere U. 01:14:54.720 --> 01:14:57.900 Und dann gehen wir eben von U aus und betrachten von dort ausgehend 01:14:57.900 --> 01:15:02.360 alle ausgehenden Kanten und updaten das Gewicht oder die Distanz von 01:15:02.360 --> 01:15:02.900 diese Kanten. 01:15:03.780 --> 01:15:07.420 Also nachdem wir das U als kleinstes Element gewählt hatten, 01:15:07.960 --> 01:15:11.360 betrachten wir alle Kanten, die von U irgendeinen anderen Knoten V 01:15:11.360 --> 01:15:15.300 erreichen über eine Kante und haben jetzt dann eben unsere 01:15:15.300 --> 01:15:27.080 Bedingungen, die wir prüfen müssen, ob hier eine Expansion praktisch 01:15:27.080 --> 01:15:28.380 erforderlich ist. 01:15:29.220 --> 01:15:33.260 Das ist dann der Fall, wenn sich die Distanz verringert im Vergleich 01:15:33.260 --> 01:15:36.660 zu dem, was wir bisher gefunden hatten an Distanz, also wenn diese 01:15:36.660 --> 01:15:40.660 Bedingung hier wahr ist, dann updaten wir die Distanz auf den neuen 01:15:40.660 --> 01:15:42.900 gefundenen kleinsten Wert für Knoten V. 01:15:44.020 --> 01:15:46.680 Also wir haben jetzt irgendwas gefunden, was besser ist als das, was 01:15:46.680 --> 01:15:47.360 wir bisher hatten. 01:15:49.340 --> 01:15:52.060 Updaten dann auch unseren Pfad entsprechend. 01:15:52.580 --> 01:15:55.680 Also diese Parent-Relation, die sagt uns jetzt eben, dass wir über den 01:15:55.680 --> 01:15:59.120 Knoten U den aktuell kürzesten Pfad erreichen. 01:16:01.660 --> 01:16:05.560 Und dann, wie wir weiter vorgehen, hängt jetzt eben davon ab, ob wir 01:16:05.560 --> 01:16:11.920 diesen Knoten V, den wir jetzt gerade in einen weiteren Schritt dazu 01:16:11.920 --> 01:16:14.840 gefügt haben zu unserem Pfad, ob der bereits in unserer Queue 01:16:14.840 --> 01:16:16.920 vorhanden ist oder ob der noch nicht vorhanden ist. 01:16:17.440 --> 01:16:20.360 Wenn der in der Priority Queue vorhanden ist, dann müssen wir da die 01:16:20.360 --> 01:16:23.080 entsprechende Distanz updaten. 01:16:23.080 --> 01:16:26.580 Also unsere neue Distanz, die wir hier berechnet hatten, muss da 01:16:26.580 --> 01:16:27.380 eingetragen werden. 01:16:27.600 --> 01:16:31.900 Also rufen wir hier dann diese Priority Queue-Methode decreaseKey auf, 01:16:32.400 --> 01:16:36.260 die eben für den Knoten V das auf den neuen Wert d von V setzt. 01:16:37.520 --> 01:16:40.860 Und ansonsten, wenn dieser Knoten noch nicht in unserer Priority Queue 01:16:40.860 --> 01:16:45.560 vorhanden war, dann ist das jetzt eben auch ein Kandidat, der eben 01:16:45.560 --> 01:16:49.800 durch das Sitzen dieser Distanz einen Wert ungleich unendlich erhalten 01:16:49.800 --> 01:16:50.140 hat. 01:16:50.300 --> 01:16:55.900 Das heißt, der jetzt unser Kriterium erfüllt, dass er auch besucht 01:16:55.900 --> 01:16:58.960 werden kann oder gescannt werden kann. 01:16:59.600 --> 01:17:02.860 Also wird er einfach eingefügt mit dem aktuell vorhandenen Wert der 01:17:02.860 --> 01:17:03.280 Distanz. 01:17:05.780 --> 01:17:08.180 Gut, dann wiederholen wir das so lange. 01:17:08.280 --> 01:17:11.660 Also erstmal die innere Schleife für alle Kanten, die von der Knoten U 01:17:11.660 --> 01:17:12.080 ausgehen. 01:17:12.660 --> 01:17:17.180 Und dann außen wiederholen wir das so lange, bis unsere Queue leer 01:17:17.180 --> 01:17:17.500 ist. 01:17:18.320 --> 01:17:22.660 Und danach ist dann unser Algorithmus schon fertig und wir haben das 01:17:22.660 --> 01:17:27.100 Ergebnis berechnet, die beiden Arrays d für die Distanz und Parent, 01:17:27.720 --> 01:17:30.100 die uns eben diese Fahrtinformationen enthält. 01:17:32.720 --> 01:17:37.780 Okay, eigentlich ein relativ überschaubarer Algorithmus, wenn man 01:17:37.780 --> 01:17:39.900 diese Priority Queues verwendet. 01:17:40.800 --> 01:17:45.800 Und schauen wir uns das vielleicht nochmal kurz an einem Beispiel an. 01:17:48.000 --> 01:17:50.800 Ja, also Sie sehen, man fängt mit dem Startknoten an. 01:17:51.660 --> 01:17:54.540 Die hier ist unsere Initialisierung, dass wir den Startknoten und die 01:17:54.540 --> 01:17:57.000 Distanz Null in der Queue ablegen. 01:17:57.160 --> 01:18:00.280 Dann wählen wir auch den als erstes Startelement aus. 01:18:01.800 --> 01:18:07.780 Und dann läuft der Algorithmus eben entsprechend ab, so wie wir es uns 01:18:07.780 --> 01:18:08.780 vorher angeschaut hatten. 01:18:09.920 --> 01:18:13.700 Da würde ich auch Sie darum bitten, sich das zu mal anzuschauen, wenn 01:18:13.700 --> 01:18:16.700 Sie wirklich Schritt für Schritt sich anschauen wollen, wie der 01:18:16.700 --> 01:18:17.840 Algorithmus hier arbeitet. 01:18:18.520 --> 01:18:23.420 Das ist eigentlich jetzt nichts weiter groß Überraschendes zu dem, was 01:18:23.420 --> 01:18:24.780 wir uns vorher schon angeschaut hatten. 01:18:25.220 --> 01:18:27.860 Und einfach nochmal jetzt hier eben angegeben, welche Operationen 01:18:27.860 --> 01:18:28.320 auftreten. 01:18:28.500 --> 01:18:31.400 Das ist Delete Min, dann eben diese entsprechenden 01:18:31.400 --> 01:18:35.940 Relaxationsschritte, die uns diese Nachfolgeknoten dazunehmen. 01:18:39.940 --> 01:18:43.940 Stattdessen möchte ich jetzt noch in den verbleibenden circa fünf 01:18:43.940 --> 01:18:49.420 Minuten noch kurz die Laufzeit betrachten, die dieser Algorithmus hat. 01:18:51.040 --> 01:18:54.180 Also schauen wir uns ganz schnell an, die Initialisierung, dieses 01:18:54.180 --> 01:18:59.520 Array initialisieren, wie groß ist das Array, Anzahl der Knoten, die 01:18:59.520 --> 01:19:00.160 vorhanden sind. 01:19:00.680 --> 01:19:04.220 Für Anzahl der Knoten haben wir immer den Buchstaben N verwendet, für 01:19:04.220 --> 01:19:05.920 Anzahl der Kanten immer den Buchstaben M. 01:19:06.140 --> 01:19:10.940 Also diese Initialisierung läuft in O von N ab, genauso wie Parent 01:19:10.940 --> 01:19:11.880 Initialisierung. 01:19:12.500 --> 01:19:16.140 Diese Sachen hier gehen sogar, also das Initialisieren des 01:19:16.140 --> 01:19:18.360 Startknotens geht sogar in konstanter Zeit. 01:19:18.520 --> 01:19:20.700 Das geht auf jeden Fall auch in O von N. 01:19:21.240 --> 01:19:26.240 Also die Initialisierung geht insgesamt in Zeit O von N, diese Zeile 01:19:26.240 --> 01:19:26.480 hier. 01:19:26.840 --> 01:19:29.100 Und dann haben wir eben unsere große Schleife, die die Knoten 01:19:29.100 --> 01:19:29.840 abarbeitet. 01:19:30.040 --> 01:19:34.700 Und wenn wir uns jetzt hier anschauen, erstmal nicht wie viel Zeit 01:19:34.700 --> 01:19:37.680 jede Operation benötigt, sondern nur wie häufig sie ausgeführt werden. 01:19:37.860 --> 01:19:43.020 Hier, dann sehen wir, diese Operation hier, die uns den nächsten 01:19:43.020 --> 01:19:48.340 Knoten auswählt, die kann maximal über alle Knoten des Graphs gehen. 01:19:49.220 --> 01:19:52.120 Und die Anzahl der Knoten im Graph ist N, also kann die maximal N mal 01:19:52.120 --> 01:19:52.860 durchlaufen werden. 01:19:53.580 --> 01:19:56.120 Und ansonsten haben wir danach immer alle bearbeitet. 01:19:57.120 --> 01:20:00.100 Also jeder Knoten wird ja nur einmal berücksichtigt, weil danach wird 01:20:00.100 --> 01:20:00.640 er gelöscht. 01:20:02.020 --> 01:20:07.820 Dann haben wir hier die Operation, die über die Kanten geht, als so 01:20:07.820 --> 01:20:10.760 grobe Abschätzung wie häufig oder wie viele Kanten es geben kann, die 01:20:10.760 --> 01:20:12.300 hier von der Knoten U ausgehen. 01:20:13.040 --> 01:20:15.760 Gesamtzahl der Kanten im Graph ist M, also ist es auf jeden Fall durch 01:20:15.760 --> 01:20:16.540 M geschränkt. 01:20:17.500 --> 01:20:22.220 Und das heißt, diese innere Schleife hier wird M mal durchlaufen. 01:20:23.680 --> 01:20:30.120 Und hier dieser letzte Schritt, dieses Insert, das ist eine Operation, 01:20:30.580 --> 01:20:33.960 die N mal durchlaufen wird. 01:20:36.620 --> 01:20:40.180 Genau, also wenn man sich das jetzt anschaut, im Grunde haben wir oft 01:20:40.180 --> 01:20:42.120 sehr viele Operationen, die sehr schnell gehen. 01:20:42.260 --> 01:20:46.120 Also diese Vergleiche sind eigentlich direkt nur Zugriffe, die man mit 01:20:46.120 --> 01:20:47.880 Off und Eins durchführen können. 01:20:48.880 --> 01:20:51.200 Dann haben wir eigentlich nur an Operationen, die mehr Zeit benötigen. 01:20:51.300 --> 01:20:55.240 Das ist die Leadmin für unsere Priority Queue, die Crease Key und das 01:20:55.240 --> 01:20:55.600 Insert. 01:20:56.760 --> 01:20:59.360 Und wenn man sich dann anschaut, was ist die Gesamtlaufzeit des 01:20:59.360 --> 01:21:06.000 Algorithmus, die ist dann eben M mal für die Kantenbetrachtung. 01:21:06.440 --> 01:21:09.640 Also müssen alle Kanten irgendwann mal betrachtet haben oder im 01:21:09.640 --> 01:21:15.300 schlimmsten Fall also M mal für dieses Decrease Key maximal 01:21:15.300 --> 01:21:19.380 aufgerufen, N mal das Leadmin und N mal das Insert. 01:21:21.240 --> 01:21:23.360 Also auch hier wird das M praktisch über alle insgesamt 01:21:23.360 --> 01:21:27.760 Schleifendurchläufe gelesen, wie oft wir eine Kante betrachten. 01:21:27.920 --> 01:21:30.020 Nachdem eine Kante einmal betrachtet wurde, wird sie nicht noch ein 01:21:30.020 --> 01:21:30.880 weiteres Mal betrachtet. 01:21:31.360 --> 01:21:33.120 Daher eben diese Angabe hier. 01:21:34.420 --> 01:21:39.080 Und jetzt hängt es eben wieder davon ab, wie man diese Datenstruktur 01:21:39.080 --> 01:21:43.380 wählt für die drei Operationen Insert, Decrease Key und Leadmin. 01:21:43.880 --> 01:21:47.780 In dem ursprünglichen Algorithmus von Dijkstra war da keine Priority 01:21:47.780 --> 01:21:56.260 Queue gewählt, sondern einfach eine ganz normale Darstellung über ein 01:21:56.260 --> 01:21:57.220 Array zum Beispiel. 01:21:57.640 --> 01:22:00.300 Ich weiß jetzt nicht genau, was im Paper da verwendet wird, aber Array 01:22:00.300 --> 01:22:01.600 hätte diese Eigenschaften. 01:22:01.900 --> 01:22:05.120 Einfügen kann man in den ZO von N, zumindest amortisiert. 01:22:05.760 --> 01:22:08.360 Decrease Key geht auch in O von N, wenn man die Elemente direkt 01:22:08.360 --> 01:22:09.220 adressieren kann. 01:22:09.700 --> 01:22:12.240 Und Leadmin muss man dann eben die Liste durchlaufen, um das 01:22:12.240 --> 01:22:13.380 entsprechende Element zu finden. 01:22:14.900 --> 01:22:20.140 Mit dieser Basisdatenstruktur, wenn man das jetzt hier einsetzt, kommt 01:22:20.140 --> 01:22:23.960 man eben auf eine Laufzeit von O von M plus N². 01:22:25.440 --> 01:22:34.740 Also sie ist linear in der Summe von Kantenanzahl und Knotenanzahl 01:22:34.740 --> 01:22:35.260 quadriert. 01:22:37.400 --> 01:22:45.380 Das M kann ja auch maximal N² sein, also durch N² ist es beschränkt. 01:22:45.500 --> 01:22:51.600 Und wenn man wenig Knoten... einfach diese Formel hier, wo wir es 01:22:51.600 --> 01:22:52.580 nicht weiter interpretieren. 01:22:54.360 --> 01:22:58.100 Aber bessere Datenstruktur, um das Minimum zu finden, sind ja die 01:22:58.100 --> 01:23:01.620 Prioritätslisten oder Priority Queues. 01:23:02.240 --> 01:23:04.820 Und wenn Sie sich dann nochmal daran erinnern, was da die Komplexität 01:23:04.820 --> 01:23:09.080 war, dann war das für das Insert Log von N, Decrease Key auch in Log 01:23:09.080 --> 01:23:10.560 von N, Leadmin auch in Log von N. 01:23:10.640 --> 01:23:12.660 Das heißt, alle Operationen können wir in den Insert Log von N 01:23:12.660 --> 01:23:13.120 durchführen. 01:23:13.700 --> 01:23:15.900 Wenn wir das jetzt dann wieder in unsere Formel einsetzen, kommen wir 01:23:15.900 --> 01:23:17.520 auf eine bessere Gesamtlaufzeit. 01:23:17.920 --> 01:23:22.360 Also wir haben da nicht M plus N², sondern M plus N mal Log N. 01:23:23.300 --> 01:23:27.360 Also mit Priority Queues können wir da eine bessere Laufzeit 01:23:27.360 --> 01:23:27.940 hinbekommen. 01:23:28.980 --> 01:23:34.640 Und jetzt als allerletzte Folie noch kurz einen Ausblick, was noch 01:23:34.640 --> 01:23:35.360 ginge. 01:23:36.160 --> 01:23:40.430 Es gibt eine Datenstruktur, die so ein bisschen ähnlich wie Priority 01:23:40.430 --> 01:23:43.790 Queues ist, aber ein klein bisschen anders. 01:23:43.910 --> 01:23:48.490 Diese Fibonacci Heaps und diese Fibonacci Heaps erlauben diese 01:23:48.490 --> 01:23:50.510 Operationen noch eine etwas andere Laufzeit. 01:23:50.830 --> 01:23:53.770 Die hatten wir uns auch schon mal nur so zum Vergleich bei Priority 01:23:53.770 --> 01:23:54.850 Queues schon angeschaut. 01:23:55.410 --> 01:23:58.690 Einfügen in O von N, Decrease Key in O von N amortisiert. 01:23:59.510 --> 01:24:01.730 Also im Schnitt über viele Operationen. 01:24:02.230 --> 01:24:04.970 Und das Löschen in O von Log N. 01:24:05.350 --> 01:24:09.590 Und damit kommen wir dann auf eine noch bessere Laufzeit, wo eben nur 01:24:09.590 --> 01:24:13.150 noch nicht das M mit Log N noch multipliziert werden muss, sondern man 01:24:13.150 --> 01:24:15.810 einfach nur M plus N Log N hat. 01:24:17.250 --> 01:24:22.350 Und das heißt, damit hätte man dann eine theoretisch sehr gute 01:24:22.350 --> 01:24:26.590 Laufzeit für den Algorithmus, wobei hier die konstanten Faktoren für 01:24:26.590 --> 01:24:28.210 diese Fibonacci Heaps etwas größer sind. 01:24:28.810 --> 01:24:34.610 Also im Prinzip, wenn Sie mit dem, was Sie zur Vorlesung haben, diesen 01:24:34.610 --> 01:24:38.410 Dijkstra Algorithmus mit Priority Queues implementieren, hätten Sie 01:24:38.410 --> 01:24:41.930 auch schon ein sehr gutes Ergebnis, was auf großen Datenstrukturen 01:24:41.930 --> 01:24:43.250 schon laufen würde. 01:24:44.610 --> 01:24:46.410 Gut, damit Schluss für heute dann. 01:24:46.790 --> 01:24:49.370 Nächsten oder jetzt im kommenden Mittwoch eine Probeklausur und 01:24:49.370 --> 01:24:50.690 nächsten Montag sehen wir uns dann wieder.