Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Dijkstra Algorithmus (deutsch)
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 42 Zeilen
- 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
- 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
- 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.
- diestrecke zwischen zweidten oder S symbolisierenßerdem markieren wir uns spä immer wir einen Knoten schonucht
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- ist ja schon besucht also wir haben zwei neue Knoten zur Auswahl einmal e und einmal
- 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
- 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
- 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
- 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
- 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
- mit 14 also gehen wir hierhin der Weg ist so entstanden und wir haben jetzt die Möglichkeit das Z noch mal ab abzudaten
- 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
- 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
- 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
- hier notiere dann ist auch einfach klar die Werte die jetzt bei dem Knoten stehen ähm sind die Werte wie ich am
- 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
- 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
- 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
- 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
Zum Nachlesen
SpannbaumEin Spannbaum eines Graphen kann in linearer Zeit entweder durch Tiefensuche oder durch Breitensuche gefunden werden. Beide Algorithmen untersuchen den …
InformatikAls einfache Rechengeräte leisteten Abakus und später der Rechenschieber unschätzbare Dienste. 1641 konstruierte Blaise Pascal eine mechanische …