Video 11-12: Kürzeste Wege

0:03 Im letzten Abschnitt zu den Grafen schauen wir uns endlich das aus der ersten Anwendung, aus der ersten Motivation bekannte kürzeste Wegeprem an. Also damals angeteasert durch wie finde ich in einem Straßennetzwerk am schnellsten von A nach B und den werden wir uns jetzt formal zuwenden. Dafür haben wir noch mal eine letzte Variante von Grafen, wenn wir genau hinschauen. Äh im Allgemeinen zumindest wollen wir das auf gerichteten Grafen anschauen. Für Straßennetze könnte man sagen, äh die meisten Straßen sind keine Einbahnstraßen. Ähm, aber äh die kann ich ja dann trotzdem durch eine Kante in die hin und rü Rückrichtung darstellen. Wenn ich Einbandstraßen grundsätzlich mit erlauben möchte, dann bin ich direkt in dem gerichteten Grafen und die neue Variante ist also jetzt ein gerichteter und kantengewichteter Grafen. Ja, ansonsten eigentlich sehr ähnlich zu dem, was wir eben hatten. Auch die Implementierung wird sehr ähnlich sein.

1:04 Und äh das Problem fragt jetzt z.B. wie komme ich am schnellsten von der 0 zur 6 und dann äh kann ich eben so einen gerichteten Fah lang laufen, wo ich also die Kanten in der richtigen Richtung verwenden muss und wir werden uns wieder dafür interessieren, was ist die die kürzeste Gesamtdistanz? Ich summiere also die Kantengewichte auf. Neben den offensichtlichen Anwendung ähm in dem Rotenplanen und und sonstigem gibt's auch hier wieder eine ganze Reihe von mehr oder weniger offensichtlichen Anwendungen. Und weil das so ein so ein witziges nischiges, aber sehr ähm optisches ähm Beispiel ist, lassen Sie mich das einfach kurz zeigen, weil ich glaube, niemand weiß, was SAM Carving ist, oder? Und das ist Seam Carving. Es ist eine eine Art völlig und sie sehen an diesem Windows 55 Stil von den Fenstern, das ist alles altes Zeug. Das hat nichts mit Deep Learning oder KI zu tun. Äh, das ist eine ähm Kontext Content abhängige Art Bilder zu vergrößern oder zu verkleinern, die natürlich irgendwo die Bilder dann schon verzerrt und lügt. Aber auf ähm diversen Beispielen ähm funktioniert es besser, dass man Bilder vergrößert und verkleinert, indem man letztlich kürzeste Wege löscht.

2:28 Und das ist hier sozusagen gezeigt. Ich will einen kürzesten Weg von oben nach unten oder von links nach rechts finden. Und der kürzester Weg heißt hier eben ein Weg mit möglichst wenig Farbwechseln zwischen den Pixeln und dann kann man noch so ein bisschen spielen, was genau Farbwechsel jetzt bedeutet. Äh, das erklären Sie dann hier. Und ähm äh von wann war das? 18 Jahre. Okay, genau.

2:57 Also eine ähm halbwegs alte Idee, aber irgendwie ganz ganz ganz nett und optisch erstmal äh vielleicht beeindruckend und kosten natürlich Bruchteil von all den äh Deep Learning basierten Verfahren, um mit Bildern zu arbeiten. Ähm offensichtlichere Varianten ähm sind die Routenplanung.

3:14 An der Stelle geht's noch mal um die Frage, was wollen wir eigentlich? Was ist genau das Problem? ähm wie hier schon rot vorgehoben. Ich kann natürlich dieses Problem mit kürzesten Wegen in verschiedene Art fragen. Für eine Routenplanung habe ich eigentlich einen ST Pfad, also von einer Quelle zu einer Senke, von Start zu Ziel.

3:37 Das ist eine die Variante, die man in der Routenplanung gerne hat. Ähm, natürlicher für die Algorithmik ist aber die Variante, wir haben einen Startknoten und suchen den kürzesten Weg zu allen anderen. Das äh stellt sich raus, ist algorithmisch sozusagen die natürlichere Frage oder darauf können wir die ähm die Lösung auf natürlichere Weise geben, werden Sie sehen. Und wichtige zweite Frage ist, was haben wir denn so für Gewichte auf den Kanten? Wenn Sie an Straßenkarten und an Gesamtweg, Länge oder Strecke oder Zeit denken, dann macht natürlich überhaupt nur irgendwie was hier in diesem unteren Bereich sind. Ähm euklidische Distanzen hieße die Knoten sind wirklich Punkte in einer Ebene oder in dem in dem äh hochdimensionalen Raum von mir aus. Und die Distanz ist einfach die klitische Distanz zwischen den Punkten. Aber das muss ja nicht so sein. Ähm insbesondere wenn das Fahrzeit ist auf einer Straße, kann durchaus sein, dass da eine Straße äh länger ist als die Summe von zwei anderen und so spämm werden also da wenig Annahmen machen wollen, aber dass es nicht negative Gewichte sind, das werden wir hier festhalten wollen.

4:53 Also die zwei ist das, was wir uns rauspicken. Ähm es gibt dann in dem Buch bzw. in effiziental Algorithmen äh natürlich noch andere Varianten. Äh vielleicht fragen Sie sich, was soll das überhaupt, wann wann macht es denn Sinn, dass eine Kante negatives Gewicht hat? Und es gibt durchaus Anwendungen, wo das total viel Sinn macht. Eine ist äh ist im Buch genauer beschrieben, das Arbitrageproblem. Wenn sie verschiedene Währungen haben mit Wechselkursen, dann kann es manchmal sein, dass äh von Dollar zu Pund zu kanadischen Dollar zu Euro und wieder zu Dollar zu tauschen Ihnen am Ende Geld generiert, weil die Wechselkurse gerade bescheuert sind. Und wie findet man das raus? Das ist genau ein ein Problem, wo es negative Kantengewichte geben kann. Also durchaus ähm ab und zu sinnvoll in manchen Anwendungen. Wir werden das hier aber verbieten. Also unsere ähm Kanten sind immer nicht negativ. oder positiv.

5:55 Kreise im Graf sind grundsätzlich zu tolerieren. Ich denke, sonst ist das Wegeprblem oft zu langweilig. Aber wir werden keine negativen Kreise haben, weil wir gar keine negativen Gewichte haben. Wenn Sie ein bisschen drüber nachdenken, kürzeste Wege, wenn es in dem, wenn es in dem Graf eine Option gibt, im Kreis zu laufen und damit Geld zu generieren oder Zeit zu sparen, indem ich immer weiter im Kreis laufe, dann ist die Idee von dem kürzesten Weg so ein bisschen hinfällig. Also ist klar, dass das ein Problem ist. Ähm, den werden wir uns hier aber entziehen, indem wir alle Kanten, unsere Kostenfunktion bildet die Kanten auf R+ ab, weil ich wollte das eigentlich immer so schreiben. R größer 0, dann haben wir diesen Ärger vom Tisch.

6:44 damit ist dann auch ähm übrigens diese Einschränkung hier unten ist gegeben, wenn die Kanten immer äh echt positives Gewicht haben, dann macht es nie Sinn länger im Kreis zu laufen. Das heißt, es wird immer einen günstigsten Weg geben. Entweder kann ich dann noch was rauslöschen, wo ich einen Umweg gegangen bin oder ich habe einen kürzesten Weg. Es gibt endlich viele insgesamt, damit ist dann das erstmal ähm gegeben, wenn der Graf zusammenhängend ist. Okay, also vielleicht noch mal unsere Annahmen in explizit statt nur so verteilt. Die Kantengewichte sind positiv, vielleicht präziser, wir sind in dem gerichteten Graf.

7:53 Das jetzt formal aufschreiben möchte. Für jeden Knoten gibt's einen Weg vom Startknoten zu diesem Knoten. Das reicht uns. Wie gesagt, einige der anderen Annahmen sind dann, wenn man allgemeinere Probleme anschaut, werden wir uns aber für Algorithmen und Datenstrukturen verkneifen müssen. Wie modellieren wir die Grafen? Wir haben jetzt ja noch eine neue Variante, ne? Gerichtete und gewichtete. Das heißt, es gibt noch mal eine Dopplung. Es gibt jetzt eine gerichtete Kantenklasse, die ist im Wesentlichen so wie die äh andere gewichteten Kantenklasse, aber ich habe eben jetzt dedizierten Start und Endpunkt von der Kante. Das heißt, ich kann die auch so benennen und das Gewicht ist wie wie bis wie bisher. Ähm, auch hier würde ich wahrscheinlich comparable implementieren wollen, um die Kanten nach ihrem Gewicht zu vergleichen.

8:48 Dann äh kann ich das natürlich den Java Code gießen mit der offensichtlichen Implementierung. Da ist genau gar nichts spannendes passiert. Ähm für den Graf selbst auch ganz analog zum ungerichteten Fall. Ich kann jetzt eben ein gerichtetes Kantenobjekt hier hinzufügen. Meine Adjazslisten verwenden die gerichteten Kantenobjekte. Und was hat sich sonst geändert? gar nichts. Ähm sieht dann in der Darstellung mit den Objekten auch so aus, ähm wie wir es eben schon gesehen haben. Ich habe jetzt natürlich, weil es gerichtete Kanten sind, das Kantenobjekt nur in einer der Adzenlisten. Äh ich kann dann, dass ich hier von der 5 zur 4 komme, sehe ich in der Liste von der 4 äh nicht mehr unbedingt, außer dass es hier ausgerechnet die Kante in beide Richtungen gibt. Perfektes Beispiel rausgegraben. Ähm aber z.B., dass ich von der 2 zur 7 komme, sehe ich in der Adzenliste von der 7 nicht. Auch das implementieren wir in Java auf die einigermaßen äh offensichtliche Weise, genauso wie für die ungerichteten Grafen.

9:56 Äh auch hier natürlich die Kante füge ich nur einmal ein, nicht in beide Richtungen. Dann können wir uns dem kürzesten Wegeproblem zuwenden in der Variante, wie wir sie oben definiert haben. Das heißt, das kürzeste Wegeproblem Shortest Paths bekommt einen solchen Graf gerichtet, kantengewichtet und einen Startknoten, von dem aus ich die Wege berechnen möchte. Das muss ich festlegen. Nachdem das dann gelaufen ist und diesen berühmten Algorithmus von Dextra ausführt, zu dem wir dann gleich kommen, kann ich mit den zwei Methoden hier die Distanz zu irgendeinem anderen Knoten mir ausgeben lassen und auch den Pfad, also den expliziten kürzesten Weg. Und wir werden ähm ja, kommen wir gleich zu.

10:43 Das ist nur eine kurze Demo, mit dem man dann so eine Ausgabe generieren kann. eine Beobachtung und an der Stelle kommt ins Spiel, dass diese Variante mit dem Single Source Shortest Path stand das schon mal irgendwo auf der Folie, das SSSP Problem Single source path problem. Das ist was wir hier lösen. Das hat eine angenehme Eigenschaft, denn diese Lösung, die die Wege, die wir da ausgeben, die sind immer in Form eines Baums gegeben. Das heißt, ähm wenn ich von einem Startknoten zu einem anderen Knoten laufe auf einem kürzesten Weg, dann sind auch alle sozusagen Präfixe von diesem Pfad. Wenn ich zwischendrin die Lust verliere weiterzulaufen und bei dem anderen Knoten stehen bleibe, dann ist das auch ein kürzester Weg zu diesem Knoten. Wenn das nicht so wäre, dann könnte ich ja diesen Präfix ersetzen durch den noch kürzeren Weg und hätte einen noch kürzeren zu meinem eigentlichen Ziel. Und deswegen kann ich diese kürzesten Wege immer als Baum im Graf darstellen mit S als Wurzel und dann äh Kanten zu sukzessive allen anderen Knoten.

12:11 Ähm hier ist z.B. ein ein etwas degeneriertes Beispiel. Der äh Raum besteht hier nur aus so zwei Pfaden, die von null weglaufen. Im Allgemeinen kann sich das natürlich auch verzweigen mit beliebig vielen ausgehenden Kanten von einem Knoten. Was heißt das für uns algorithmisch? Das bedeutet, dass wir uns ähnlich wie in der Tiefenuche und der breitensuche, da klingelt vielleicht was, ein Array merken können, von welchem Knoten sind wir zu einem bestimmten Knoten gekommen in diesem kürzeste Wege Baum.

12:47 Und mit diesem Edge2 Array kann ich dann diese ähm Fade zu einem Knoten auch bequem ausgeben. Da muss ich dann einfach nur rückwärts durch dieses Edge to Array laufen und dann den Pfad rückwärts ausgeben. Also was wir speichern werden, ist die Distanz zu einem Knoten und eben woher ich kam im kürzesten Wegebaum, als ich diesen Knoten erreicht habe. Und dann kann ich diese Fatto Operation äh implementieren. Genauso wie wir es getan hatten für die ungewichteten Grafen mit Tiefen und Breitensuche. Breitensuche hauptsächlich. Ähm, ich habe einen Stack von Kanten. Ich fange bei meinem ähm Knoten an, der mich interessiert und laufe dann immer die Kanten, die zu diesem Knoten geführt haben, rückwärts ab, bis ich bei meinem Startknoten angekommen bin, bis es kein der Startknoten selbst hat null als als Edge2. kann ich damit aufhören. Ich hätte auch fragen können, wann ich beim Startknoten bin, aber weil ich die Kantenobjekte habe, ist das schneller. Und dann nehme ich das Kantenobjekt auf und da das ein Stack ist, liefert es dann man drüber iteriert die den Pfad in der richtigen Reihenfolge.

14:09 Okay, wie machen wir das aber jetzt? Wie berechnen wir kürzeste Wege in so einem Graf in diesem Szenario? Ja, also fester Startknoten. Ähm, man könnte natürlich auch wieder sowas wie bei der Breitensuche machen und sagen, ich fange bei dem Knoten an und guck mal so lokal drumrum, was läuft da. Ähm, um das ganz strukturiert und etwas allgemeingültiger zu machen, äh gibt's hier ein allgemeines Kriterium und das ist die Operation einer Kantenrelaxierung.

14:50 Der größte Vorteil von dem Framework ist, dass es auch für andere Algorithmen funktioniert und auch wenn negative Kantengewichte ins Spiel kommen. Ähm wie gesagt, werden wir nicht machen. Bei uns ist es dann etwas einfacher, aber das allgemeine Framework ist trotzdem hübsch zu verstehen. Ähm, die Idee ist eine äh Kante relaxieren bedeutet, ich zeige Ihnen das erstmal optisch in der ähm in der Metapher. Stellen Sie sich vor, Sie haben hier Ihren Startknoten und alle anderen Knoten sind erstmal auf Distanz unendlich festgepinnt, weil wir noch nichts über sie wissen. Von dem Knoten null laufe ich los und nehm seine ausgehenden Kanten. Das ist hier diese Feder, die aktuell gespannt ist, weil ich den Knoten 1 künstlich weit von null weghalte. Eine Kante relaxieren heißt jetzt, ich nehme eine solche Kante und lass die zusammenschnurren auf die Länge, die sie haben möchte, die ihrem Gewicht entspricht oder ihrer Länge entspricht. Und sie zieht damit der Knoten null ist fest verankert, sie zieht dann diesen Knoten 1 näher zu sich heran.

16:00 Das bedeutet aber, dass jetzt andere Kanten gespannt wurden, weil die jetzt auch ähm eine Distanz überbrücken von hier ähm dem Abstand 0,2 kann man nicht wirklich lesen zu unendlich. Also, sie müssen sich jetzt hier vorstellen, grafisch ist es so gemalt, dass ich die ähm auf einem Kreis gemalt habe, aber eigentlich gibt's nur den Radius. Der Radius, der Abstand vom Mittelpunkt ist eigentlich das einzige, was gilt. Eigentlich sollten die Punkte alle auf einem Punkt auf dem Kreis sein, aber dann können sie nichts sehen. Deswegen ähm ist sozusagen dieser Abstand hier und der Abstand hier genauso lang. Das ist die Idee von der Kantenrelaxierung. Ich habe künstlich den Start und Endpunkt weiter auseinander aktuell, als die Kante es erlaubt, als die Kante es möchte und ich lasse die zusammenschnurren und hole damit einen Knoten näher ran. Ähm, wenn ich das von dem Knoten 1 ausmachen würde, dann habe ich z.B. hier die Kante, die gespannt ist. Die geht von Distanz 0,2 zu unendlich hat aber nur Länge 6. Das heißt, wenn ich die zusammenziehen lasse, dann holt ihr den Knoten fünf so ein bisschen näher ran.

17:10 Und hier noch einmal, was so schön war, äh die Kante ist kürzer, das heißt, die zieht den Knoten zwei deutlich näher ran. Okay, das ist das ist die Metapher, die Sie im Kopf haben sollten. Äh formal heißt es natürlich immer, ich habe irgendeinen Distanz zu dem Knoten Von, wo die Kante losgeht und ich habe der Distanz zu dem Knoten B, wo die Kante hinführt. Und die Kante relaxieren heißt überprüfen, ob über diese Kante, also der aktuelle Pfad von S zu V hat eine gewisse Länge, bringt es mir was diesen Pfad um diese Kante VW zu verlängern, um günstiger zu W zu kommen als bisher. So wie in diesem Beispiel hier ist die Antwort manchmal ja und dann sollte ich das tun, dann sollte ich mir das merken. Und all diese Schritte zusammen, also prüfen ist es günstiger mit den aktuellen Distanzen und wenn ja, sich merken, dass jetzt der beste Pad zu W über V führt und diese neue Länge hat.

18:08 All diese Schritte zusammen bezeichnet man als eine Kantenrelaxierung. Okay. Und wie gesagt, denken Sie an diese gespannten Federn, dann ist es vielleicht relativ intuitiv. in Code ähm macht's genau das. Ich prüfe die aktuelle Distanz. Bin ich weiter von zu W bisher unterwegs als über V? Wenn ja, dann merken wir uns das.

18:38 Und das Hübsche ist jetzt, dass ähm unter diesen Eigenschaften Kanten relaxieren genau das Richtige tut. Also, wenn wir so einen gerichteten, kantengewichteten Graf haben und die ähm die Distanzen so eingetragen sind, dass der Startknoten Distanz null hat und wir haben in den Distanzen die Länge irgendeines Pfades von S zu V. Das heißt, also vielleicht noch nicht die echte Distanz, noch nicht den kürzesten Weg, aber einen gültigen oder unendlich, wenn wir noch keinen kennen. Beides ist okay. Ähm, dann gilt für jede Kante diese Ungleichung, dass die Distanz von B höchstens die Distanz zum V plus diese Kante ist.

19:42 Äh, ich denke, ich hätte ähm diesen Teil hier lesen sollen, deswegen bin ich gestauchelt. Äh, wir haben Einträge in diesem Distanzarray. Das hier sind Bedingungen, die wir dann erfüllen.

19:54 Aber diese ähm aktuellen Distanzen repräsentieren genau dann die endgültigen kürzeste Wegeedistanzen, wenn diese drei Bedingungen erfüllt sind. Der letzte Schritt ist nämlich die Abbruchbedingung im Algorithmus, die am Anfang noch nicht gilt. Das ist ja genau das, was wir mit der Kantenrelaxierung dann überprüfen. Wenn aber alle drei zusammen gelten, dann sind die Distanzen alle zusammen optimale Distanzen von dem kürzesten Weg. Und dafür muss eben hier diese dritte Bedingung gelten, dass sozusagen eine Relaxierung irgendeiner Kante nichts mehr tun würde.

20:43 Also wie wir das verwenden wollen, ist ein allgemeiner Algorithmus. könnte sagen, relaxiere solange Kanten. Ähm, der ist dann auch hier. Fange an mit der Distanz zu S ist 0. Distanz zu allem anderen ist unendlich. Und solange diese drei Bedingungen von eben noch nicht erfüllt sind, relaxiere irgendeine Kante und dann prüfe noch mal. Und mit dem mit dem Beweis hier sehen wir, dass das immer kürz kürzeste Wege findet. Ähm nur in aller Kürze, warum ähm sind diese drei Bedingungen äh die das Richtige, wenn die drei Bedingungen gelten, seltsame Artes zu schreiben, äh wenn die wenn die Bedingungen ähm nicht erfüllt sind, die ersten zwei, das lassen wir immer gelten und das hier ist auch im Algorithmus immer sichergestellt. Aber angenommen, wir haben hier eine Ungleichung in die andere Richtung, also die Distanz bei w ist echt größer. Na ja, dann gibt's eben einen kürzeren Pfad über V zu W. Also ist das Ganze noch nicht eine optimale äh kürzeste Wegedistanz.

21:59 Und umgekehrt, wenn diese drei Bedingungen erfüllt sind, dann kann man durch geschicktes Aufsummieren genau die kürzesten Wege generieren. Also dieses hier entlang eines potenziellen kürzesten Weges folge ich. Für jede Kante kriege ich diese Ungleichung, die stehen hier. Wenn ich die aufsummiere, dann kürzen sich da ähm ich die nacheinander verwenden, dann habe ich die Distanz zu W, was die Distanz zum letzten Knoten hier ist, ist eine nach oben beschränkt durch die Summe aller diese dieser Kanten und das war aber ein kürzester Pfad und damit ist die Distanz von W nach oben beschränkt durch diesen Pfad. Tatsächlich funktioniert das hier für jeden Pfad, aber auch für einen kürzesten. Also ist das hier die Länge von dem kürzesten Weg.

23:01 Damit können wir also diesen allgemeinen Algorithmus formulieren, wie man kürzeste Wege berechnen kann. Ähm funktioniert im Wesentlichen genauso, wie äh der Beweiser sagt. Was jetzt offen ist, ist, wie finden wir denn diese ähm wie machen wir das denn effizient, dass wir die nächste Kante finden, die wir noch relaxieren können? Und an der Stelle hängt's davon ab, was für einen Graf wir haben.

23:27 Wir werden uns auf das erste Beispiel beschränken. Das ist der Extras Algorithmus. Da ist die Annahme, dass wir eben keine negativen Kantengewichte haben, dann funktioniert der immer. Ähm, es gibt dann noch zwei andere Varianten, die dem gleichen Schema folgen. Schauen wir uns aber nicht an.

23:53 Okay, vielleicht lassen wir einen kleinen Teil für Donnerstag noch übrig. Ähm, ein paar Worte, aber vorab. Ezg Dextra ist einer der ähm grün Informatiker, der da auch sehr prägend war, auch weil er gerne mal kernige äh Sprüche rausgehauen hat. Ja, mehr oder minder äh konkret. hat großen Einfluss gehabt auch jenseits von diesem Algorithmus für ähm die Disziplin des Programmierens und so weiter. Können sich mal in Ruhe noch äh reinlesen, wenn Sie mögen.

24:30 Äh Daxas Algorithmus funktioniert ähm im Wesentlichen über folgende Analogie. Wir lassen nämlich zuerst die intuitive Variante zeigen. Die Analogie ist genauso wie für die Breitensuche, dass wir von einem Startknoten aus eine Welle durch den Graf schicken. Also ein paralleler Algorithmus, den wir nicht genauso implementieren, aber von der Idee, was passiert ist, wir lassen eine Welle durch den Graf laufen und wann immer die Welle einen Knoten erreicht, wissen wir, dass es seine Distanz und man könnte auch den Weg, über den er erreicht würde, sich aufheben. Grundsätzlich ähm der Unterschied zur Breitensuche, wo wir das die gleiche Analogie hatten, vielleicht noch mal ähm optisch zur Erinnerung, damit Sie sich erinnern, das war in breiten Suche, wie das aussah. Ich habe dann immer diese Distanzlayer gehabt, wo gleichzeitig eine ganze Reihe von Knoten jetzt erreicht wird.

25:35 In Deixas Algorithmus muss ich die Geschwindigkeit, mit der das Wasser über die Kanten fließt, an die Kantenlänge anpassen. Dementsprechend ähm läuft das hier, okay, das ist bisschen zu langsam. Äh, das Wasser läuft hier unterschiedlich schnell über die Kanten. Die Kante ist kürzer, das heißt, da bin ich zuerst da und demnach wird dieser Prozess über die Zeit so ein bisschen ähm asynchronis äh asynchron ablaufen. Und ähm jetzt habe ich hier noch so ein Rennen von den letzten drei Kanten, wer wir das schaffen und einer erreicht eben dann diesen letzten Knoten zuerst. Also anschaulich ist das, was wir simulieren wollen. Sie können sich auch vorstellen, wir laufen da als äh Ameisen oder irgendwas mit gleicher Geschwindigkeit die Kanten lang. Und weil manche Kanten länger sind, dauert's länger. Und wenn ich mich einen Knoten erreiche, teilen wir uns auf, spawnen neue ähm Leute, die explorieren und alle Kanten, die davon ausgehen, werden dann entsprechend verfolgt.

26:44 Dich Algorithmus ist im Wesentlichen eine Simulation von diesem kontinuierlichen Prozess. Wir können natürlich dieses Wasser laufen lassen nicht so wirklich gebrauchen, um den Algorithmus zu simulieren. Äh, aber sie sehen auch hier in diesem Szenario, da passiert lange einfach gar nichts. Die Animation muss jetzt irgendwelche Bildchen malen, aber für die Distanzen passiert ja nur dann was, wenn zu diesem Zeitpunkt einer der Wasserströme einen neuen Knoten erreicht oder einen Knoten erreicht. Also, man kann diese eigentlich kontinuierliche Simulation reduzieren auf diskrete Zeitschritte zu denen, was Interessantes passiert. Und die diskreten Zeitschritte sind immer dann, wenn ein ein Wasserschluck eine Kante äh das Ende erreicht. Alle anderen Zeitpunkte dazwischen sind eigentlich langweilig. Und was wir also tun werden, ist ganz genau diese diskrete äh Zeitsimulation für diesen kontinuierlichen Prozess zu bauen, indem man einfach ähm vorab wir planen sozusagen voraus, wenn ich hier starte, dann ähm dann weiß ich, diese drei sind jetzt eine Weile unterwegs und ich weiß genau, aktuelle Zeit + 5 passiert hier was, aktuelle Zeit + 8 passiert hier was, aktuelle Zeit + 9 passiert hier was. Die ganzen Zwischenschritte dazwischen, die interessieren mich nicht. Da passiert nichts.

28:07 Und das also das nächste Mal, dass was Interessantes passiert, weck mich nach fünf Zeitschritten auf, ist dieser Teil hier oben. Und jetzt, wo dieser Knoten erreicht ist, weiß ich, nach Zeit 5 + 15 wird Knoten 3 erreicht. merke ich mir also als Event, zu dem ich wieder aufwachen muss, stell ein Timer. Nach Zeit 5 + 4 werde ich hier diesen Knoten 7 erreichen. Was ich zu dem Zeitpunkt nicht sinnvoll schon wissen kann, ist, dass eigentlich Knoten 7 schon vorher erreicht wurde über diese Achterkante. Also, ich lege eine Liste von zukünftigen Zeitstritten, zu denen was spannendes passiert und wo ich noch mal gucken muss. Und äh zu jedem Zeitpunkt nehme ich mir dann den nächsten Zeitpunkt zu dem, was passiert als als Event raus und simuliere, was da genau geschieht. Und dann kann es mir passieren, dass ich ein paar Events noch mal habe, bei denen ich aufgeweckt werde, wo eigentlich gar nichts mehr zu tun ist. Das hat sich sozusagen schon erledigt. Das sehe ich aber dann eventuell erst, wenn ich zu diesem Zeitpunkt noch mal drauf gucke.

29:14 Das ist letztlich die Idee hinter DXTRAS Algorithmus. Ähm, also einerseits diese kontinuierliche, wir lassen Wasser entlang laufen und zweitens ähm diese Simulation durch eine diskrete Events Simulation ersetzen.

29:36 Ein Baustein, den wir dafür brauchen, kennen Sie schon und so wie ich es beschrieben habe, ist es vielleicht auch intuitiv. Ich habe ähm vielleicht sollte ich das notieren.

30:11 Was brauche ich, um diese Eventsimulation zu machen? Ich muss zu gewissen Zeitpunkten vorhersagen können, wann das nächste potenziell interessante Event passiert und ich muss dann, wenn ich mit dem aktuellen Event fertig bin, das nächste Event in der zeitlichen Reihenfolge finden. Und das ist eine Priority Queue, in die ich Elemente einfügen kann mit dem Zeitpunkt, zu dem sie relevant werden. und ich möchte das nächste Event, was noch nicht verarbeitet ist, rausholen und wir fügen Events ein über den Zeitpunkt, den wir jeweils berechnen können. Witzigerweise ist die der Zeitpunkt identisch zur Distanz vom Startpunkt. Das haben sie in der Simulation auch gesehen. Das Wasser breitet sich mit Einheit Einheitsgeschwindigkeit aus. Dementsprechend passieren die Events genau in nach so so viel Zeitschritten wie die Distanz zu dem Knoten im Graf ist von unserem Startknoten ist.

31:19 Das könnte man so machen, ähm, dass man sozusagen ähm jedes Mal, wenn eine Kante neu zu einem äh wenn ein Knoten erreicht wird, fügen wir Events ein für alle ausgehenden Kanten. Das sind aber dann relativ viele.

31:33 ähm eine Optimierung ist noch zu sagen, wenn ich sehe, dass äh ich den den gleichen Knoten hier wieder erreiche, also ich weiß eigentlich, ich werde Knoten 7 nach acht Zeitschritten erreicht haben und dann noch mal später den Knoten zu besuchen. Hier ist nur einen längeren Weg finden. Brauche ich eigentlich nicht. Das heißt, an dem Zeitpunkt, wo ich Knoten 1 hier verarbeite und sehe, ich habe eine Kante mit Länge 4 Z7, die Knoten 7 in Zeitschritt 9 erreicht, kann ich mir eigentlich sparen, den überhaupt äh anzuschauen. und umgekehrt ähm wenn es später also es kann auch eine langlaufende Kante geben, die z.B. hier prognostiziert Knoten 6 würde ich nach was auch immer 29 Schritten erreichen. Das habe ich relativ früh rausgefunden. Das heißt, ich würde Knoten 6 nach Distanz 29 spätestens finden. Es gab dann aber später hier einen einen anderen Weg, der sagt: "Nee, nee, nee, das passiert ehrlich gesagt früher." Und dann macht es eigentlich keinen Sinn, dieses Event 29 hier noch zu erhalten. Die Simulation behält das drin, aber unsere Implementierung möchte eigentlich das nicht. die möchte eigentlich jeden Knoten nur das erste Mal besuchen.