Dijkstra Algorithmus (deutsch)
bleeptrack
https://www.youtube.com/watch?v=2poq1Pt32oE

Transkript (automatisch erstellt)

0:01 hallo und herzlich willkommen bei beliebtck heute geht's um den Dix Algorithmus den benutzt man um den kürzesten Weg zwischen zwei oder mehr
0:12 Knotenpunkt zu finden wir schauen uns heute die Variante für einen Knotenpunkt an dazu habe ich schon mal einen Grafen vorbereitet und unser Ziel ist es vom
0:24 Startpunkt s hier unten den kürzesten Weg zum Ziel Z hier oben zu finden der Graf hat kchte die habe ich hier immer heschrieben die könten z.
0:35 diestrecke zwischen zweidten oder S symbolisierenßerdem markieren wir uns spä immer wir einen Knoten schonucht
0:44 haben das mache ich immer indem ich den rot einkringel und wir merken uns no einen zuszlichen distanzwert den schrebe ich immer an die Seite des Knotens und
0:53 der wird der beimknoten wird er mit null initialisiert und bei den anderen Knoten erstmal mit unendlich dann können wir eigentlich schon loslegen also wir sind
1:02 am Startknoten S und vom Startknoten S aus erreichen wir drei Knoten den Knoten a den Knoten B und den Knoten g jeweils mit diesem Aufwand einmal mit 5 mit 2
1:14 und mit 4 das bedeutet wir können die Werte hier updaten das heißt von S nach a komme ich mit dem Aufwand 5 von S nach B komme ich mit dem Aufwand
1:25 2 und von S nach G komme ich mit dem Aufwand 4 das war eigentlich schon mal meine erste Aufgabe jetzt kann ich zum nächsten
1:33 Knoten laufen und dazu suche ich mir den Knoten aus den ich mit dem geringsten Aufwand erreichen kann denn dikra ist ein greedy Algorithmus und greedy macht
1:42 praktisch jeden Zug das momentan für ihn am beste manchmal sucht er sich das Maximum raus in dem Fall sucht man sich also eher das Minimum weil man möchte
1:50 die kürzeste Strecke haben das heißt wir laufen von S nach B und damit ist B praktisch besucht jetzt können wir mal schauen welche Knoten wir von B aus
2:01 erreichen wirreichen einmal a und einmal C und über B also B ist hat ja schon den Aufwand 2 von B nach A kommt noch der Aufwand 1 dazu das heißt wir haben
2:12 praktisch eine Wegstrecke von 3 das ist kleiner als 5 deswegen können wir den Wert hier updaten das heißt 3 ist die kürzeste Möglichkeit um a zu erreichen
2:22 und wir kommen noch an C ran bei C hätten wir dann 10 stehen die 2 von B hier und die zusätzliche 8 hier oben okay also wir haben die Punkte A g
2:36 und C entdeckt zwischen die einen von denen müssen wir uns erst entscheiden zu welchem wir laufen und der kürzeste hier wäre a mit 3 also geht's zu a hier
2:49 rüber von A entdecken wir nur noch einen neuen also den haben wir schon aber können wir nur noch einmal überprüfen das ist der Knoten C den könnten wir
3:00 jetzt über a mit der mit dem Aufwand 6 erreichen nämlich 3 den Aufwand um nach A zu kommen und dann mit der zusätzlichen dre hier bis zum C wäre
3:08 also 6 das ist kleiner als die 10 können wir updaten so jetzt haben wir zwei Knoten zur Auswahl wo wir hingehen können
3:16 einmal das G mit der 4 unten und das C mit der 6 und die vier ist kleiner also schauen wir uns erstmal das G hier unten an vom S aus so von dem G aus können wir
3:28 einen Knoten neu erreichen das ist das D da können wir also auch die Strecke hier updaten das wären dann 6 4 + 2 sind 6 so und jetzt stehen wir V einem
3:40 kniffligen Punkt für die nächste Auswahl wir müssen uns zwischen C und D entscheiden die haben beide die gleiche Gewichtung würde sagen das hängt jetzt
3:49 ein bisschen von der Implementierung ab ich würde sagen wir nehmen in dem Fall das C weil das haben wir als erstes entdeckt das wäre wahrscheinlich in
3:55 unserer Liste weiter vorne also gehen wir zum C über das a hier dann sind wir beim C upsa vom C aus können wir zwei Knoten
4:09 neu entdecken das D und das E zum e kommen wir mit dem Aufwand 12 zum D kommen wir mit dem Aufwand 10 das ist größer als die 6 bringt uns also
4:23 nichts das zu notieren weil wir schon den kürzeren Weg zu d gefunden haben okay also wir entscheiden uns zwischen E und D D hat den kleineren Aufwand also
4:32 gehen wir zu d das funktioniert über g dann sind wir hier so von D aus gibt's zwei neue Knoten das C hier hinten müssen wir uns nicht mehr anschauen das
4:43 ist ja schon besucht also wir haben zwei neue Knoten zur Auswahl einmal e und einmal
4:50 F G halt entscheiden müssen wir haben noch nicht geupdatet sorry okay wir updaten erstmal die Werte 16 hätten wir für e das ist größer als 12 bringt uns
5:00 nichts m beim F haben wir noch kein Wert da würde 14 hinkommen 6 und 8 sind 14 so jetzt können wir uns entscheiden
5:10 zwischen E und F e macht den kleineren weg mit der 12 also gehen wir dahin die 12 ist hier über diesen Weg entstanden so okay vom E aus finden wir
5:24 einen neuen Knoten das ist das Z das hat auch noch kein Gewicht das können wir also auch updaten also haben wir 19 okay genau einen anderen Knoten
5:36 können wir nicht abdaten von E aus weil D und C ist schon besucht so jetzt müssen wir uns wieder entscheiden zwischen z und F F ist momentan kleiner
5:47 mit 14 also gehen wir hierhin der Weg ist so entstanden und wir haben jetzt die Möglichkeit das Z noch mal ab abzudaten
6:00 allerdings würden wir auf den Aufwand 11 und 14 25 kommen das ist größer bringen uns also nichts so das heißt wir machen jetzt den
6:10 letzten Schritt zu Z über diesen Weg weil der hier der kleinere ist und damit sind wir bei Zeit angekommen das war's schon so
6:21 funktioniert dira man kann das wenn man das etwas tabellenförmig aufschreibt bekommt man praktisch auch gleich alle Werte wenn ich das mir nämlich so wie
6:31 hier notiere dann ist auch einfach klar die Werte die jetzt bei dem Knoten stehen ähm sind die Werte wie ich am
6:39 schnellsten zu diesem Knoten komme und wenn ich mir einfach für jeden Knoten auch merke von wo ich gekommen bin muss ich ja mehr oder weniger sowieso machen
6:45 dann habe ich jetzt praktisch auch sowieso mit rausgefunden wie ich von von S am schnellsten zu G zu d etc komme also nicht nur zu Z so das war's schon
6:55 wie immer habe ich eine Aufgabe dabei für euch so weg damit das ist fast der gleiche Graf ich habe ein bisschen geändert und
7:05 vor allem die Kantengewichte geändert und wie immer gibt's die Lösung unter dem Video ich hoffe es hat euch Spaß gemacht und bis zum nächsten Mal tschüss