Video 11-13: Dijkstras Algorithmus

0:03 Um eine diskrete Events Simulation zu implementieren, brauchen wir eine Möglichkeit, diese zukünftigen Events mit einem Zeitstempel in der Zukunft so zu ordnen, dass wir dann jeweils effizient das nächste eintretende Event äh verarbeiten können. Und das ist eben genau das, was eine Priority Queue leistet, eine Min Priority Queue für die Zeit, in der wir Events einfügen können mit einem bestimmten Zeitstempel. Ab dann äh zu einem zu zukünftigen Zeitpunkt wird der Knoten vom Wasser erreicht und dann muss was passieren. Dann muss ich berechnen, was äh als nächstes für eine Wasserwelle fließt.

0:39 Und ähm wir haben dann noch die Verfeinerung, dass wir eventuell einen Knoten früher erreichen als ursprünglich bekannt. Dann können wir dstempel vorziehen. Was wir dafür brauchen ist eine Priority Queue, die auch diese Decrease Key Operation unterstützt. Dann kann ich nämlich als Event einfach den Knoten im Graf nehmen und präziser gesagt das Event ist den Knoten das erste Mal von der Wasserwelle zu erreichen. Ja, initial weiß ich darüber wenig. Das ist für alle Knoten beliebig lang weg und wenn ich dann Kanten zu einem Knoten entdecke, dann weiß ich von dem aktuellen Zeitpunkt plus Kantenlänge zu dieser Zeit zu diesem Zeitpunkt in der Zukunft wird der Knoten spätestens erreicht, vielleicht aber auch noch früher.

1:29 Die Creaske brauche ich also, um diese ähm Entdeckung eines kürzesten Wegs nutzen zu können, dass ich den Knoten früher erreiche. Und dann haben wir folgendes Problem, dass wir vorher nicht hatten, als wir uns im Kapitel äh zu Suchbäumen auch diese Priority cues oder binären HEBS angeschaut hatten. Wenn ich ein Element einfüge, dann ist es ein Objekt und das ist dann Teil von diesem von dieser Min Priority Que und das ist aber sozusagen weg aus meiner Sicht, denn die Priority queue wird das intern sie sich wie binäre Haps funktionieren in diesem Array hin und her bewegen und das ist dann nicht mehr ohne weiteres klar, wie ich ein Decrease Key eigentlich adressieren soll. Wie sage ich der Priority queue dieses Event von vorgestern? Das ist übrigens das, was ich jetzt meine und was wir vorziehen. Und eine einfache Lösung in diesem Kontext, da wir über Knoten in einem Grafen reden und die immer gleichgesetzt hatten mit den ersten Integern, äh ist das einfach ein Index. Das heißt, eine Index Priority queue identifiziert die Objekte, die in der Priority Queue eingefügt werden können mit Integern.

2:35 und ich habe eine Obergrenze dafür von Anfang an vorgegeben. Das ist genau das, was in diesem Grafkontext gebraucht wird. Deswegen reicht uns das hier und wir brauchen uns keinen keine Gedanken über den allgemeinen Fall an der Stelle machen. Wenn ich also ein Element einfüge, dann gebe ich den Index mit und sage der Priority queue, ich habe hier einen Namen, diesen Index I. Unterdem möchte ich in Zukunft mit Decrease Key auch die Priorität anpassen können. Sorge dafür, dass das möglich ist. Ähm das kann man dann auch zum Prüfen nehmen, ob ein Element drin ist. Und Delete Min reicht jetzt, wenn es den dieser Identifier zurückgibt, dann weiß ich ja extern noch, was damit gemeint ist. Die Implementierung ist aber fast genau die gleiche, die wir damals besprochen haben für für binäre Haps. Das einzige, was sich ändert, also wir hatten damals PQ als den das Array, in dem die der binäre Hieb abgelegt wurde. Ähm, blättern Sie im Gedächtnis zurück oder schauen Sie noch mal nach.

3:40 Ähm, da steht sozusagen ähm die äh das Element, das an dieser Position im Heb liegt. Also noch mal hier das Bild dazu sehen sich, wir lassen die den Index 1 immer aus und ähm dann ist hier das Element 0 ganz oben. Also PQ sagt jetzt den Index des eingefügten Schlüssels, der steht an der passenden Stelle im Hieb. Wir lassen die Stelle null aus. Das mal macht die Rechnungen mit dem zu den Eltern laufen und zu den Kindern laufen einfacher. Position 1 entspricht der Wurzel und da steht jetzt hier die Null. Das heißt, da ist es der Wert A, der da eigentlich steht. Das ist sozusagen, wie wir es bisher auch hatten.

4:34 Was neu dazu kommt, ist, dass wir auch ein eine ein umgekehrtes Array haben. Wenn ich wissen will, wo steht denn das äh der Schlüssel null, dann schaue ich in dieser Spalte von der Null in dieses QP, in das umgekehrte Array. Das ist sowas wie die umgekehrte Abbildung. und dann steht da eine 1. Das heißt an Position 1 finde ich hier die 0, die Permutation und die Umkehrpermutation. Und wann immer sie eine Vertauschung in einem der Arrays machen möchten, weil eben eine der Operationen von den HEs sagt, wir sollen das tun, machen wir die Vertauschung in dem anderen Array mit und dann wissen wir zu jedem Zeitpunkt, wo die Elemente sind. äh klingt vielleicht verwirrender als es ist. ist aber ähm tatsächlich, wenn sie den sich den Code dazu angucken, ähm straight forward als Erweiterung von was wir bei den HES hatten.

5:28 Mit dem Baustein, mit dieser Index Priority Queue können wir dann Dikas Algorithmus sehr effizient hinschreiben. Ähm, was ich was ich jetzt hier neu habe, ist eben eine Priority Cube für die Knoten.

5:42 Und ich habe äh initial extern von der Priority Que merke ich mir die Distanz, die äh ich bisher zu diesem Knoten gefunden habe. Initial unendlich für alle Knoten, außer für den Startknoten. Da kenne ich einen Weg der Länge null. Ja, wir sind schon da. Dann füge ich ähm den auch in die Prique ein. Und ab da habe ich diesen regulären Ablauf. Das nächste Event, dass ich verarbeiten muss, der Knoten, der als nächstes erreicht wird, ist das Minimum in der Priority Queue. Den verarbeite ich jetzt und ich werde dann auch, das ist die Garantie von der Simulation, nie später einen kürzeren Weg zu diesem Knoten finden. Wenn ich den hier aus der Priority Queue geholt habe, heißt das, das Wasser erreicht ihn jetzt und eben nicht früher. kann nicht rückwärts durch die Zeit fließen. Also, wir entfernen den äh und für alle seine ausgehenden Kanten rufen wir dieses Kanten relaxieren auf. Das müssen wir jetzt um eine Sache erweitern, denn das Relaxieren muss jetzt den ähm Knoten in der Priority Queue aufnehmen, um dieses zukünftige Event da zu speichern. Also konkret der alte Teil ist, wir prüfen, ist diese diese neue Kante, die wir jetzt gefunden haben, von V zu w ein kürzerer Weg zu W, als was ich bisher kannte.

6:59 Wenn dem der Fall ist, dann merke ich mir das und ich merke vermerke in meiner Event queue, es gibt jetzt potenziell einen früheren Startpunkt für B. Wird früher von der Welle erreicht und dann gibt's die zwei Optionen. Falls der schon in der Priority queue ähm eingefügt wurde irgendwann vorher, dann mache ich Decrease key und falls es noch nicht vorkam, dann füge ich ihn jetzt ein. Die zwei Fälle müssen wir an der Stelle unterscheiden, weil innerhalb von der Priority Queue die Abfolge ein bisschen anders ist. Einmal fügen wir ein neues Element ein und lassen es hochschwimmen. Ähm im anderen Fall von Decrease Key springen wir irgendwo in die Mitte und lassen das Element eventuell noch weiter aufsteigen. In Detail ein bisschen anders, deswegen müssen wir den Fall unterscheiden. Konzeptionell ist aber ähm beides einfach dieses zukünftige Event jetzt vorverlegen.

7:52 Schauen wir uns das noch einmal in ähm ein Beispiel an. Da ken wir vielleicht alles gerade noch drauf. Also, wir haben hier einen gerichteten Graf. Das ist auch ähm das Beispiel, was in den Folien auch verwendet wurde. Äh hier sind die Adjazlisten, nach denen werden wir vorgehen. Und hier haben wir einen Bereich für die Priority Queue. Ja, wir fangen bei Knoten null an und berechnen jetzt die Distanzen zu allen anderen Knoten.

8:31 Zuerst gehen wir durch die Adjazliste von diesem Knoten null und vermerken für die ausgehenden Kanten, welche Knoten erreiche ich damit jetzt kürzer. Ich relaxiere diese Kante. Bisher habe ich zu ähm den Knoten hier ähm keinerlei äh Distanz gekannt. Das heißt, das ist jetzt äh die tauchen dann hier auf. Die unendlichen Initialisierungseinträge tauchen leider nicht auf. Äh, wer w ich mir muss man noch anpassen. Wenn man ähm den Knoten jetzt mit Distanz 5 erreicht, dann steht hier fünf als die garantiert späteste Zeit, wann die Wasserwelle diesen Knoten erreicht. Das ist die Innvariante. Jetzt haben wir diese Kante relaxiert. Dann gehen wir zur nächsten Kante. Nach Zeit 9 erreiche ich diesen Knoten 4. Merke ich mir auch. Spätestens dann sehe ich den. und die dritte ausgehende Kante, die sieben ebenso. Okay, jetzt enthält die Priority queue drei drei Events mit den Zeitstempeln 5 8 und 9. Und ich habe jetzt meinen Knoten null abgearbeitet, dessen Priority Queue, dessen dessen Adenzliste ist ausgeschöpft.

9:41 Den muss ich nie mehr betrachten. Damit bin ich mit dem fertig. Und der nächste Schritt ist das Minimum aus der Priority Queue suchen. In dem Fall ist es der Knoten 1, den ich mit nach Zeit 5 erreiche. Jetzt bin ich also hier bei dem Knoten 1 und weiß für diesen Knoten wird es nie eine frühere Zeit geben, ihn zu erreichen. Ich habe sozusagen alle Events bis zu den Zeitpunkt abgearbeitet und jetzt mache ich für den Knoten das gleiche. Er hat diese ausgehenden Kanten. Für die zwei kannte ich bisher gar kein Pfad. wird also auf jeden Fall der beste sein. Das heißt, ich kriege hier einen Eintrag von 5 + 12 und was wir auch sehen ist in in dunkelbraun ist dieser ähm Edge to Array eingetragen. Also über welchen über welchen Vorgängerknoten habe ich diesen Knoten oder diesen Knoten das erste Mal betreten. In Ver 2 steht da aktuell die ein drin. Also über diese Kante bin ich zur zwei gekommen.

10:37 Das kann sich aber später noch mal aktualisieren. Vielleicht gibt's einen kürzeren Weg. Okay, was haben wir noch für ausgehende Kanten? Wir gehen noch zur drei. Die haben wir auch noch nie gesehen. Das heißt, da passiert das gleiche. Ist der erste Eintrag. Zur sieben hatte ich schon vorher einen Pfad und tatsächlich ist die 8 weniger als 5 + 4. Das heißt, da passiert nichts. Der neue Weg ist länger. Das heißt, ich würde jetzt auch meine Priority Queue gar nicht ändern, denn der Knoten hat schon eine kürzere Zeit eingetragen. Da passiert also nichts und die Kante wird sozusagen verworfen.

11:11 Damit sind wir mit allen ausgehenden Kanten von eins durch. Jetzt geht das ganze Spiel von vorne los. Der allgemeine Schritt ist, wir suchen das nächste Event aus der Priority Queue. Was ist der nächste Knoten, der jetzt erreicht wird? Das ist Knoten 7 nach Zeit 8. Also schaue ich mir den an und dann geht das Spiel von vorne los. Okay. Ja, vielleicht dann jetzt ein Ticken schneller. Knoten 7 ist weiter unten. Hier sind eine ausgehenden Kanten zu 5 und 2.

11:40 Zur fünf kennte ich kannte ich noch keine Distanz. wird also auf jeden Fall äh der kürzeste Weg sein. Zur 2 hatte ich bisher eine Distanz von 17 und jetzt habe ich 8 + 7 15. Das heißt, hier habe ich jetzt mal eine Aktualisierung. Die Kante hier, woher kürzester Weg ist jetzt diese hier und die Distanz zu 2 ist aktualisiert von 17 auf 15 runtergesetzt. Okay, damit sind wir mit den ausgehenden Kanten von Knoten 7 fertig. Der ist also verarbeitet und wir gehen zum nächsten Knoten in der Priority Queue. Das war hier die vier und schauen uns deren ausgehende Kanten an. Die hat hier diese drei da hoch. Ähm einmal zur fünf. Distanz zu 5 war bisher 8 und 6 14 und jetzt habe ich 9 und 4 13. Das also besser. Das heißt, ich biege auch hier die Kante um und merk mir die 13 statt der 14. Äh, nächste ausgehende Kante ist diese ganz lange zu se. Da haben wir noch keinen Weg gekannt. Nehmen wir auf jeden Fall. Während hier dieser lange Umweg zu 7, der ist nutzlos.

12:47 Und so geht's immer weiter und immer fort. Es passiert ab jetzt immer das gleiche. Also vielleicht einfach eben schnellurchlauf noch den Rest. Ja, das war jetzt sehr sehr schnell. Sie sehen, es kann sich zu manchen Knoten der Pfad der kürzeste ein paar mal verschieben. Im allgemeinen keine keine Schranke, wie oft das passiert.

13:21 damit sind wir mit Dexas Algorithmus im Wesentlichen durch. Wenn wir analysieren, wie lange der braucht, dann müssen wir einfach zählen, welche Operationen er auf der Priority Cube macht. Alles andere ist nämlich günstig. Das sehen Sie im Code. Ähm, also ich habe hier bisschen Initialisierung einmal über die Knoten laufen, aber was ich sonst mache außerhalb der Priority Cube Operation sind nur so ein paar ein paar Checks und dieses relaxieren, also diese Arrays aktualisieren. Aber der dominante Anteil der Kosten sind die Priority Queue Operation. Wenn der Kraft zusammenhängend ist, dann wird jeder Knoten irgendwann einmal in die Prique eingefügt und er wird auch genau einmal entfernt, nämlich wenn ich ihn dann endgültig erreiche mit der Wasserwelle das erste Mal. Äh die Crease Key, wie oft kann ich die ähm frühste Ankunftszeit aktualisieren? Das könnte insgesamt pro Kante jeweils passieren. Man muss tatsächlich ein bisschen ähm knobeln, um einen Graf zu finden, wo das tatsächlich eintritt, weil das heißt, dass man immer wieder kürzere Wege zu einem Knoten entdeckt, auch wenn man den schon x mal erreicht hat. kann man aber im Worst Case konstruieren.

14:33 Das heißt, wir haben sehr viel mehr Decrease key Aufrufe potenziell als für die anderen, denn die Anzahl Kanten könnte ja bis zu quadratisch in der Anzahl Knoten sein. Okay? Ähm, je nachdem, wie viele ähm Knoten und Kanten man so hat in den Grafen, gibt's verschiedene Möglichkeiten, diese Priority Cube zu implementieren. Die Standardversion, die wir normalerweise hier im Kopf haben, ist der binäre Hieb. der macht alle Operationen in äh logarithmischer Zeit in der Größe der Priority Que und das ist die Anzahl Knoten. Und dem ist dann die Gesamtlaufzeit für Dexas Algorithmus dominiert von diesem E mal Decrease Key. Und das sieht man auch schon Potenzial für Optimierung, wenn ich eine andere Priority queue bauen kann, wie z.B. hier diese letzte Zeile, die wir nicht besprechen werden hier in der Vorlesung. Ich sag sozusagen nur, dass es das gibt. Ähm, da kann man mit amortisierten Kosten, sie nennt sich an dieser Doubling Arrays, die Geschichte mit den Münzen, da kann man erreichen, dass sowohl Insert als auch Decrease Key über die ganze Operation Folge Konstantzeit braucht. Dafür muss man ein bisschen mehr arbeiten, wie gesagt, wen wir hier nicht machen. Damit kann ich aber die Laufzeit auf e + V log drücken.

15:50 Und wenn ich also viele Kanten habe im Vergleich zu den Knoten, dann lohnt sich das. Klammer auf in der Praxis ist es eine andere Geschichte, weil diese Datenstruktur komplizierter ist und viele Pointer verfolgt. Ähm da muss man schon sehr sehr große Grafen haben, damit sich das lohnt und dann passieren andere Dinge, aber theoretischerweise das theoretisch beste Ergebnis kriegt man mit den Fibonacci HEs und dann ist eben das die Laufzeit, während die übliche Implementierung, wie wir sie hier gebaut haben, würde äh eh mal log V brauchen. Dann gibt's noch einen witzigen Effekt. Ich kann auch ein äh eine dumme Priority Queue bauen, in der ähm das äh quasi gar nicht sortiert, vorgehalten wird und das Delete Manfach ein Scan durch das Array ist. Das ist selten eine gute Option. Wenn ich aber ganz viele Kanten habe, ist es besser als der binäre Hieb. ist so ein seltsamer Randfall, aber kann man im Kopf behalten. Ähm, eine andere Variante, auf die wir jetzt auch nicht äh im Detail eingehen werden, aber äh die aus praktischer Sicht sinnvoll ist, wenn es wenn Sie äh Gewichte haben, die z.B. kleine Zahlen kleine ganze Zahlen sind, dann kann man auch eine Spezialform von der Priority Cube bauen, die das ausnutzt und dadurch schneller wird.

17:18 Okay. Gibt es Fragen zu Dexas Algorithmus? Ja. ähm also so wie auch andere äh Graftraversierungsalgorithme, Breitensuche, Tiefensuche, all diese, äh müssen wir eine Art besucht Array speichern. Das gibt, das taucht hier nicht explizit auf. Ähm, aber im Prinzip haben wir das über die über die Priority Queue dann doch gegeben. Wenn ich einen Knoten endgültig daraus entfernt habe, dann werde ich ihn nie mehr äh besuchen. Das ist hier so ein bisschen implizit. Also die ähm die Beobachtung von Dikas Algorithmus ähm das kann ich Ihnen vielleicht woanders noch mal zeigen.

18:28 Seh nennt sich an die ähm Animation hier mit den mit den Kantenrelaxierung. Das ist auch eine speziell für Deichstas Algorithmus auf einem kleineren Graf. Die zeigt was anderes. Wenn ich hier in dem Knoten starte, ich relaxiere eine Kante und dann bringt die den Knoten näher hin. Und das war das Ende der Adzenliste von diesem Knoten null. Danach weiß ich, in diesem Radius 0,2 kann es keinen anderen Knoten geben, denn ich bin von Knoten null losgelaufen. Die einzige Kante, die aus diesem Knoten rausgeht, hat Länge 0,2 und alle Kanten haben positives Gewicht, nicht negatives Gewicht. Okay, das heißt, es kann nie mehr einen Knoten geben in diesem Radius. Sprich, wenn ich jetzt ähm den nächsten Knoten mir hole, dann hat er mindestens dieses diese Distanz 0,2. Also das Extract aus der Priority Queue gibt mir einen Knoten 0 mit Zeit 0,2 und es gibt nie mehr einen, der früher kommt. Und das bleibt auch in Zukunft so, die Zeiten, zu denen wir Knoten aus der Priority Queue holen oder diese diese Distanzen, äh die steigen monoton an, die werden nie kleiner und deshalb kann ich über das Distanzarray eigentlich so einen Visited Array realisieren. Ich muss mir nicht explizit merken, welchen Knoten ich schon abge gehandelt habe, sondern daran, indem ich meine aktuelle Zeit mit der Distanz zu dem Knoten vergleiche, weiß ich, ob ich ihn schon abgehandelt habe. Also, wenn ich hier noch ein Schritt weitergee, wir prüfen die Kanten, die von eins ausgehen, das sind die vier und dann passiert da jeweils wieder dieses Relaxieren.

20:02 Danach weiß ich alle Knoten, die jetzt in diesem inneren Kreis sind, bis zum nächsten Minimum. Da kann es nichts Weiteres geben und alle Knoten, die da innen drin sind, die sind fest an die an die Wand gepinnt. Die werden sich nie mehr bewegen können. Es kann keinen kürzeren Weg von der Null zu einem der Knoten hier drin geben, z.B. der 1, denn die habe ich alle schon abgearbeitet. Das heißt, der Vergleich von Dist to 1 mit was ich gerade an dem Wert aus der Priority queue gegeben habe, der würde mir angeben, ob ich den Knoten schon besucht habe. Auf die Weise kann man indirekt sicherstellen, dass wir den nicht noch mal besuchen.

20:43 Sie können mal äh durchspielen, was in dem Code passieren würde, wenn es negative Gewichte gibt, dann ist das alles ähm gar nicht mehr garantiert.

21:08 Da bleibt mir an der Stelle nur äh drauf hinzuweisen, dass es noch viel viel mehr zu grafen gibt, was man da tun kann algorithmisch. Ähm, insbesondere haben wir uns keine Netzwerkflüsse angeschaut. Äh, wir haben uns nicht angeschaut, was man mit negativen Kantengewichten machen kann. Und dann gibt's noch eine Reihe von anderen Fragen, die man auf Grafen haben kann. und einiges mehr davon sehen sind effiziente Algorithmen, wenn Sie denn mögen oder wenn sie denn müssen. Äh manche von ihnen werden gar keine Wahl haben und für die anderen äh hoffe ich natürlich, dass wir uns trotzdem dann wiedersehen.