Nun gut, denke wir können anfangen. Um zum Rückblick zu kommen von letzter Woche, da haben Sie die Graf-Algoritmen kennengelernt, die ersten Sie haben,

die sich geliehen was Grafen sind, welche Eigenschaften Grafen haben und alles was dazu gehört gibt es dazu noch Fragen Ihrer Seite.

Nein, gut, dann kommen wir heute nämlich zu den ersten interessanteren Graf-Algoritmen auch für eider interessanteren Graf-Algoritmen.

Wir befassen uns heute nämlich mit dem Problem der kürzesten Wege und wir lehren dafür zwei Algorithmen sehr detailliert können, dass wir der Dijkstrailgerhythmus und der Floyd-Waschel-Algoritmus sein, der Dijkstrafe für einfach, wenn ich den kürzesten Weg zwischen einen Punkt, zur einen anderen Punkt haben möchte und der Floyd-Waschel, wenn ich den kürzesten Weg zwischen allen Punkten Paaren, die es in einen Grafen gibt, berechnen möchte.

Im Kommentar dazu, die Kapitel 22 und 23 zu lesen, wenn man die Begleitliter tun noch durchgeht. Genau, so können Sie sich vorstellen, warum kürzeste Parade überhaupt interessant sind.

Man könnte einfach immer bummeln, werde auch schön. Hat der jemand Ideen, ja. Genau, wir haben das Verkehrswesen, da ist das kürzesten Weg natürlich interessant, weil wir irgendwann ankommen wollen.

Da wollen ich den durch halt Deutschland fahren, nur auf Umfonds, Nürnberg oder Erlangen nach Berlin zu kommen. Haben Sie andere Ideen, wo kürzeste Wege interessant sein könnten, also auch praktisch relevant sein könnten.

Hier vorne, Sie werden nur sicherlich ein paar Ideen haben, ja. Einfach eine Idee. Auch Verkehrswesen, wir haben zum Beispiel auch Transportwesen, also wenn wir Güter transportieren wollen.

Da aber es auch ähnlich zu Verkehrswesen, was aber auch interessant ist, zum Beispiel bei Computerspielen, ist Perfinding ein sehr beliebtes Problem, was auch für die Spielerbasis zu Problemen führen kann.

Da wollen Leute zum Beispiel kürzeste Wege berechnen lassen. Das heißt, das Problem der kürzesten Wege kann an vielen Stellen auftreten.

Und damit wir erst mal verstehen, was dieses Problem überhaupt ist, müssen wir natürlich anfangen, uns mathematisch zu definieren, damit wir da noch sinnvoll arbeiten können.

Wenn Sie sich über übrigens fragen, warum wir wieder eine Tafelanschaft haben, zum einen haben wir, also wenn Sie von hinten nicht sehen, kommen Sie gerne einfach näher vor.

Der Grund dafür ist, wir haben immer noch technische Probleme mit Guthnauts, der Software, die wir ansonsten zur Vorbereitung nutzen.

Und als Neustar Mitarbeiter an dem Lehrstück kann ich darauf leider noch nicht zugreifen. Daher haben wir an dieser Stelle noch mal eine Tafelanschaft.

Genau. So wie ist das Problem definiert? Wir haben in Erster Linie erst mal eine Eingabe für unser Problem, auf dem wir dann wollen. Wir haben ein Gewichteten und ein Gerichteten Grafen.

Unser Graf gehen mit Knoten und Kanten. Wir können auch mit ungerichteten Arbeiten, indem wir den Graf zuvor transformieren, in eben ein gerichteten Grafen.

Dazu haben wir eine Gewichtsunktion.

Wir nehmen wir sie mal weh, die von Kanten auf Zahlen abbildet. Genau, und die gibt uns einfach nur das Gewicht einer Kante zurück.

Der erste Punkt ist, wir wollen jetzt mit unserer Gewichtsunktion auch das Gewicht eines Pardes angeben können. Was ist noch mal ein Pard im Grafen-Theoritischen Setting?

Genau im Endeffekt. Das heißt, von einem Pard können wir von einem Punkt, zu einem anderen Punkt gehen, über andere Punkte, bzw. über Kanten.

So ein Gewicht, W von P, also eines Pardes, und P geben wir in diesem Fall mit Knoten an. Das heißt von 0, V1, Punkt, Punkt bis Vk.

Ist definiert über die Summe der Gewichte, die halt zu den Kanten gehören.

Manthematische lässt sich das dann wie folgt darstellen. Das heißt, wir haben die Summe von E gleich 0 bis K, das heißt, über alle Knoten, die wir da haben.

Und wir sumieren im Endeffekt das Gewicht der Kanten, wenn wir die Kanten als Tuples, zwei Knoten angeben. Das heißt hier von Vi minus 1 bis Vi. So sumieren wir im Endeffekt alle Kanten, über die unser Pard geht.

Und wir haben das Gewicht unsere Pardes.

Jetzt wollen wir natürlich, wenn wir ganz viele Parder haben, den Kürzestenpferd haben, und wie ist der definiert, wenn er einen der Kürzestepferd,

stellen wir ihn als Delta von U, V da, das heißt von U nach V, ist wie folgt definiert.

Wie nie im Endeffekt einfach nur den minimalsten Pard aus der Menge an Parden von U nach V, und das ist unser kürzester Pard.

Das heißt, wir haben das Minimum der Menge an Parden von U nach V. Damit geben wir in Endeffekt diese Menge an von allen Parden, die es halt zwischen diesen beiden Knoten geben kann, zwischen den beiden Knoten und mit Minimum extra werden.

Genau, und der dieser Pard tritt, der einen Pard zu überhaupt, einen Pard zwischen zwei Knoten gibt, muss er nicht vorliegen.

Und wenn kein Pard existiert, dann ist unser Basecase unendlich.

Genau, dann können wir einfach keinen Pard finden. So, nachdem wir jetzt die Gewichte von Kanten und dazu auch die Gewichte von Parden berechnen können, und wissen, dass der kürzeste Pard ist,

so können wir unser Problem definieren. Das kürzeste Pardepublin besteht darin, den kürzesten Weg oder Pfad von U nach V.

Das heißt, im Endeffekt wollen wir irgendein beliebigen Part für den gilt, dass VP gleich der kürzeste Pard ist.

Das heißt, wir suchen einen Pard, so dass das Gewicht des Pards entsprechen der Länge des kürzsten Pards ist.

Ja.

Das ist vollkommen richtig. Wenn ich gleich null ist, müssten wir von I bis I plus 1 gehen. Oder wir machen I1 und dann geht die vorherige Schreibweise.

Genau, ja, stimmt.

So ist unser Problem erstmal definiert, das heißt, wir wollen halt aus der Menge an möglichen Paden, den Pard finden, dessen Kosten halt irgendwie am geringsten sind, da minimalsten. Genau, jetzt haben wir noch ein bisschen mathematischer ausgerückt, was wir später dann nutzen können, wenn wir die Algorithmen dazu entwerfen und anzeigen.

So, nun gibt es von dem Problem nicht nur eine Variante, sondern wir haben vier unterschiedliche Varianten. Das, wie aufgezeichnet, die wir hier haben, ist im Endeffekt das shortest Pair-Problem zwischen Zweiknoten.

So und damit ich das nicht vergesst, wie die korrekt auszudrücken sind, haben wir hier das Single Pair, also wir haben ein einzelnes Paar an Knoten.

Schaut erst per Problem.

Das ist auch so das grundlegend, einfachste Bekannteste und auch naheliegendste Problem- oder Problemvariante zu eben den kürzesten Paden.

Was wir jetzt noch natürlich auch berechnen können, ist die erste Variante, dass wir nur einen Ausgangspoten haben, das heißt Single Source.

Schaut das Paar.

In dem Fall, bei Single Source haben wir einen starken Noten gegeben und möchten die kürzesten Faden zu einen anderen Knoten berechnen.

Für uns in dieser Vorlesung kommt in dem Fall der Deixer Albe Ortenus zum Tragen, weil der genau dieses Problem löst.

Wenn wir jetzt noch eine Single Source Variante haben, dann können wir auch Single Destination Variante haben.

Die Single Destination Variante ist im Endeffekt, wie die Single Source Variante nur, dass wir einen Ziel haben, statt einem Startknoten und jetzt von allen anderen Knoten zu diesem Ziel kommen wollen.

Diese beiden Problemen, Single Source und Single Destination sind sehr nah miteinander verwandt.