Der DIJKSTRA ALGORITHMUS (einfach erklärt)
Vložit
- čas přidán 27. 07. 2024
- ► Mein Python-Buch amzn.to/3ARMbw8 (*)
Inhalt 📚
Woher weiß ein Paket, welchen Weg es durch ein #Netzwerk nehmen muss, um von einem Router S zu einem Router Z zu gelangen? Ganz einfach! Durch ein Routing-#Protokoll, das einen #Algorithmus nutzt, mit dem man den kürzesten Weg von einem bestimmten Router zu allen anderen Routern im Netzwerk berechnen kann. Der Algorithmus, mit dem man das bewerkstelligen kann, heißt #Dijkstra-Algorithmus. Das Link-State-Routing-Protokoll Open Shortes Path First (#OSPF) nutzt diesen Algorithmus, mit dem das Wissen über die Kosten zum Erreichen von Routern innerhalb des Netzwerks aufgebaut werden kann. Als Basis wird ein Netzwerk betrachtet, das aus verschiedenen Knotenpunkten (Routern) besteht, die über Links miteinander verbunden sind. An diesen Links sind "Kosten" eingetragen. Damit ist der Aufwand gemeint, mit dem man von einem #Knoten (#Router) zu einem anderen Knoten (Router) kommen kann. Diese Quantifizierung nennt man auch #Metrik. Wenn es beim Routing nur um die Anzahl der #Hops geht (d. h. wie viele Router muss man durchlaufen, bis man am Ziel angekommen ist), dann entsprechen die Kosten an jedem Link 1. Anstelle des technischen Begriffs "Router" verwenden wir fortan "Knoten", da der Algorithmus auch in anderen Bereichen als dem Routing angewendet wird.
Vorwort 0:00
INTRO 0:03
Einführung 0:11
Der Algorithmus 1:14
Beispiel 2:33
ENDE 6:24
EQUIPMENT(*)
🎤 Mikrofon amzn.to/3N0CHCL
✂️ Schnittprogramm amzn.to/3CZ217J
💻 Mein Laptop amzn.to/3ikMd5V
🖥️ Bildschirm amzn.to/3ig3yN5
SUPPORT
► Patreon / florian_dalwigk
► PayPal
► Unterstütze mich durch einen Kauf auf Amazon. Für dich entstehen keine Mehrkosten! (*) amzn.to/3LgyglY
SOCIAL MEDIA
💬 Discord: / discord
💡 Website: www.florian-dalwigk.de
📱 TikTok: / florian.dalwigk
🤳 Instagram: / florian.dalwigk
🐦 Twitter: / florian_dalwigk
📧 E-Mail: mailto:info@florian-dalwigk.de
(*) Bei den Amazon-Links (https.//amzn.to/???????) handelt es sich um Affiliate-Links. Wenn du etwas über diesen Link kaufst, bekomme ich eine kleine Provision. Der Preis ändert sich nicht, wenn du über diesen Link einkaufst. Vielen Dank für deine Unterstützung.
► Mein Python-Buch amzn.to/3ARMbw8 (*)
► Ethical Hacking mit ChatGPT amzn.to/3Qf9mID (*)
► Hacking mit Python amzn.to/3pxVnmh (*)
(*) Bei den Amazon-Links (https.//amzn.to/???????) handelt es sich um Affiliate-Links. Wenn du etwas über diesen Link kaufst, bekomme ich eine kleine Provision. Der Preis ändert sich nicht, wenn du über diesen Link einkaufst. Vielen Dank für deine Unterstützung.
Ich bin blind und das Video ist so gut und ausführlich erklärt, dass ich es durch bloßes Zuhören verstanden habe.
Ich finde gut, dass du jeden Schritt ausführlich erklärt hast, ohne abzukürzen oder zusammenzufassen, auch wenn es sich dann immer wiederholt hat. So prägt sich der Ablauf besser ein.
Danke für das Lob! Genau das war das Ziel ;)
Bisher bestes Video zum Thema! Wenige Aufrufe dürfen nicht abschrecken. Übrigens das Titelbild wirkt sehr professionell
Vielen lieben Dank :) Mittlerweile hat es ja schon einige Klicks ;)
Absolute Spitzenklasse !!! Im Gegensatz zu anderen Beiträgen wird am Ende auch erklärt, was man mit der (Ergebnis)tabelle genau machen muss, um den kürzesten Weg zu finden. Sehr anschaulich wird der Algorithmus bildlich mit den Farbanzeigen erklärt inklusive der Anzeige der Iterationsschritte. Zum ersten Mal habe ich auch den Sinn und vor allem die Nutzung der Tabelle verstanden. Jetzt fühle ich mich auch erstmals in der Lage diesen Algorithmus selbst programmiertechnisch umzusetzen.
Toll, das freut mich :)
danke cheffe, schreibe in 30 min Klausur
Ich hoffe, die Klausur lief gut 😃
sehr schöne visualisierung :D
Danke :)
Vielen Dank für die super verständliche Erklärung! Gutes Tempo, sodass man gut mitgekommen ist, gute Veranschaulichungen und immer wieder gleiche Formulierungen für gleiche Sachverhalte... Das hat mir beim Verstehen sehr geholfen, danke nochmal!
Vielen Dank für dein Feedback :) Sehr gerne!
irgendwie fühlen sich die 30 min der Vorlesung, die mit diesem algorithmus verbracht wurden, als verschwendet an, wenn man das in 6 min so gut erklären kann..danke :D
Super, das liest man gerne 🙂
bei uns hat der prof über ne stunde rumgestammelt und danach hatte man mehr fragen als antworten^^
@@TheXoronLP kenn ich 😂
Heilige... unser Lehrer in der Burfsschule hat das Thema nur für 5min angeschnitten, dass es existiert und wir es in der nächsten Klasse (3te Stufe) benötigen werden. Aber durch Corona konnte nicht länger auf das Thema eingegangen werden. Ohne dein Video wäre ich wahrscheinlich aufgeschmissen gewesen.
Es freut mich sehr, dass ich dir weiterhelfen konnte!
Sehr einleuchtend erklärt! Definitiv eines der besten Videos zum Dijkstra-Algorithmus, vielen Dank :)
Vielen Dank und natürlich gern geschehen :)
Danke! Solche Inhalte sind mittels Animationen einfach so viel verständlicher, danke für deine Mühe
Gerne :) Freut mich, dass ich dir weiterhelfen konnte!
Das hätte ich für die letzte Klausur gebraucht!
Vielleicht ein Video über Graphen, Spannbäume, Minimaler Spannbaum und evtl. einen Beweis, ob ein Spannbaum in einen Graphen liegt? :D
Mist! Hätte ich das früher gewusst ;) Hoffentlich klappt es diesmal mit den Videos vor deiner nächsten Klausur :)
@@Florian.Dalwigk Also diese Themen würden mich auch sehr Interessieren. Schreibe im Januar ne Klausur in dem fach operations research und da sind die ja Thema. Cooles video !!!
Oh yes, das schreib ich am samstag
Wirklich wirklich gut. Vor allem das durchgehende Wiederholen beim Erklären. Vielen Dank!
Sehr gerne 😊
Gut erklärt. Top!
Du hast mein Leben gerettet, bitte noch mehr Videos zu Algorithmen 😍
Haha, super :)
Wirklich tolle Erklärung! Bitte mach weiter Videos!!!
Gerne! :)
Du hast mir meinen Tag gerettet 👍🏻
Sehr schön erklärt, einfach Top!!!!!!
Vielen Dank für dein liebes Feedback :)
Top erklärt, dankeschön!
Gerne
Danke für deine Arbeit!
Gerne!
Danke dir hat mir echt geholfen
Gerne
Sehr gute Erklärung hat mir viel geholfen, danke!
Das freut mich :)
Richtig, richtig gut erklärt
Vielen Dank 😊
Sehr hilfreich, vielen Dank!
Das freut mich! Sehr gerne :)
Sehr gut erklärt, danke
Gerne :)
super erklärt, respekt
Vielen Dank :)
schnell und hut erklärt danke
Gerne 🙂
Ich studiere zwar noch nicht Informatik aber das war echt interessant, weiter so!
Das freut mich :) Viel Erfolg, wenn du dein Informatikstudium beginnst!
oha, die Videos sind ja richtig gut
Oh, danke :)
Tolle, einfach Erklärung! Danke 😄
Gerne doch :) Soll ich zum Dijkstra-Algorithmus noch ein Video mit Aufgabe+Lösung machen (so wie hier: czcams.com/video/CHo2jF4JYjM/video.html)? :)
Algorithmen verstehen ja, das wäre super :)
Hier ist das Beispiel zum Dijkstra Algorithmus: czcams.com/video/L5uuj2F61pc/video.html :)
Algorithmen verstehen dankeschön 😊
Vielen Dank!
Gerne 🙂
Super erklärt! Dankeschön :)
Gern geschehen!
@Tornax 07 yoooooo, ich wollte gerade Philips Vortrag vom Informatikcamp wiederholen, und wen seh ich hier? XD
Aber das Video ist echt gut! 👍😁
?
@@Florian.Dalwigk Sorry, der Kommentar ist von nem alten Mitschüler und Kumpel, war etwas unerwartet darüber in einer random Kommentarspalte zu stolpern 😅
sehr geiles video :D
Schön, dass es dir gefallen hat 🙂
Ich bin begeistert
Hervorragend :)
Du hast es verstanden die wichtigsten Informationen kurz und verständlich darzustellen, eine Eigenschaft welche viele Lehrende leider nicht besitzen.
Danke dir :)
Diskrete Strukturen war auf jeden Fall die interessanteste Vorlesung im Informatik Studium :)
Das kann ich mir vorstellen! Vor allem, weil es vielen Informatikern beim Denken und Konzeptionieren hilft.
super erklärt
Sehr gerne
TOP!
Danke! ❤
Gerne
Du rettest meinen aller Wertesten... :D
Danke, gutes Video!
Gerne :) Viel Erfolg beim Lernen weiterhin :)
@@Florian.Dalwigk Vielen Dank! Online Diskrete Mathematik zu lernen ist echt undankbar & da helfen halt solche Videos enorm weiter :D
In der Tat :) Ich erinnere mich da auch an meine Studienzeit zurück ;)
Ein Video über Künstliche Intelligenz wäre nice
Kommt sehr bald :) Ich erarbeite für meinen VHS-Kurs gerade eine kleine Präsentation zu diesem Thema - daraus mache ich dann auch ein Video.
Gamechanger.... Einfach alles verstanden🥳
Nice :) Das freut mich wirklich sehr!
Oha Danke
algo comment, weil das video bombe is
Vielen lieben Dank :)
In 6min auf Anhieb das verstanden, was die Professorin in einem Semester nicht geschafft hat vernünftig zu erklären :D Vielen Dank!!🙏
Das freut mich wirklich sehr :) Viel Erfolg für die Prüfung!
@@Florian.Dalwigk Danke! :)
Moin, super Video! Kannst du sowas auch noch mal zu A* machen?
Danke dir.
Mal schauen ..m
wie lernst du, machst dir notizen?
Wie sieht di Laufzeit des Algorithmus aus?
top.
🙏
Schreibe heute meine Abschlussprüfung und frische mir nochmal fix mein Wissen auf, ich hab das im Unterricht nie so gelernt :D, nie dinge in Tabellen eingetragen etc, ich weiß echt nichts was mein Lehrer uns beigebracht hat
Ich wünsche dir viel Erfolg 🍀
Noch eine Frage dazu ... Wenn der Graph gerichtet ist. Im Prinzip wird immer wieder ein neuer Ausgangsknoten bestimmt. Aber nehmen wir an, ich bin bei einen Knoten A, der nach oben gerichtet ist (Pfeil nach oben) und von unten erreicht werden kann (nur 1 Richtung Pfeil nach oben). Wenn ich jetzt schon bei A bin, darf der Algorithmus die Richtung des Pfeil inogieren und zzm unteren Knoten springen? (Unter Annhame das dieser Pfeil nach unten z.B.: 2 als Kosten hat und der Pfeil nach oben 7)
Nein, die Richtung des Pfeils ist entscheidend! Du kannst auch nicht in einer Einbahnstraße plötzlich umdrehen, weil es effizienter ist ;)
Frage zu 4:34 ...Hier wird A als kostengünstigster besuchter Knoten (20) genommen aber D ist mit 10 doch günstiger...Oder?
D wurde zu diesem Zeitpunkt schon besucht ;)
@@Florian.Dalwigk Aber A doch auch?
@@motomoto3655 nein a wurde da noch nicht besucht, so wie ich das verstanden habe, bedeutet besucht, dass man zu dem knoten gegangen ist und dann alle nachbarn dieses knoten überprüft hat. Wenn du von S aus die Kosten für den Weg zu A prüfst, dann hast du A damit noch nicht besucht. Also er hat alle von S abgehenden Wege geprüft und bei allen Nachbarn die Kosten eingetragen. Außer D und A waren zu dem Zeitpunkt noch alle anderen auf unendlich und D hatte mit 10 somit den kleinsten Wert. Ich denke eine gute Regel ist, dass wenn ein Knoten noch mindestens einen Nachbar hat bei dem unendlich steht, dann bedeutet, dass das dieser Knoten noch nicht besucht wurde. In die andere Richtung funktioniert diese Regel aber nicht.
Hi( Ps: gutes Video)
Hi( PS: Danke)
Eine Frage zu deinem Beispiel: Angenommen es gäbe beim Knoten D keinen Weg Richtung C und A, die restlichen Werte wären gleich.
Bei S wäre dann der günstigste Weg immer noch zum Knoten D, und dieser wäre der nächste Knoten. Doch dann bin ich doch irgendwie blockiert? Es sind zwar noch nicht alle Knoten besucht, aber von D führt nur ein Weg zu S aber S wurde bereits besucht und D ist auch der günstigste Knoten im Graph. Wie wäre dann das vorgehen oder übersehe ich etwas?
Ok ich habs glaub verstanden, es wird einfach mit A weiter gemacht, weil A die geringsten Kosten hat. Dabei ist es egal, ob es einen Weg zu A gibt oder nicht.
Ja
Welche Knoten muss ich abarbeiten, wenn es zwei Knoten mit den selben kosten gib?
Wird im Video erklärt
komm zu tu dortmund da würde deine Erklärungsmethod viele Probleme lösen :D
Würde dieser Algorithmus nicht (quasi) unendlich lange laufen wenn er so die Wegkosten im Internet berechnen würde?
Die Zahl der Knoten wäre ja hier wie ich annehme sehr viel größer, oder übersehe ich hier etwas?
Endlich, da die Anzahl der Wege im Internet ebenfalls endlich sind. Nur eben sehr lange ...
Kleiner Copy & Paste Fehler in der Beschreibung ", wie man überprüfen kann, ob eine eingegebene IBAN-Nummer korrekt ist." ...
Ansonsten cooles Video :-) Bitte auch noch den Bellman-Ford Algorithmus vorstellen
Hoppla! Danke für den Hinweis :) Klingt super. Ich denke, dass ich dazu vlt. sogar noch diese Woche ein Video mache. Ich habe damals auch auf CZcams nach einem Video zu diesem Algorithmus gesucht und leider kein passendes gefunden :/
@@Florian.Dalwigk kleiner Reminder: Video ist noch ausständig :-)
Blöde Frage, aber ist das ein Flussdiagramm? Bzw. Wie könnte man dies zu einem umschreiben? :D
Nein, das ist die Darstellung eines Netzwerks durch einen Graphen. Du kannst aber einen Zustandsautomaten zu einem Flussdiagramm umschreiben.
Gleich Informatik LK Klausur xD
Du rettest mich lmao
Viel Erfolg!
@@Florian.Dalwigk Danke! Hab geschrieben und hast mir mein Arsch gerettet! Hoffen wir Mal auf ne gute Note xD
Ich drücke dir die Daumen, dass alles geklappt hat :)
Ich glaube jeder ist hier in der Nacht vor der Klassenarbeit...
:)
Ich drücke dir ganz fest die Daumen! Schreib gerne, wie es gelaufen ist.
Morgen info abi jungs
Viel Erfolg euch allen! :)
@@Florian.Dalwigk dange, Glück brauche ich aufjedenfall morgen
Und, wie war es?
@@Florian.Dalwigk ja war ganz ok, denke mal so ne 3 is drinne, die kellerautomaten aufgaben am ende habe mich ein wenig runtergezogen
Ah, okay! Danke dir für die Rückmeldung ;)
ich liebe dich
^^
Man speichert eigentlich die gesamte Distanz in der Spalte Kosten, da ja gilt: d(v) < d(w) + w(v,w) sein.
Das machen wir hier auch.
@@Florian.Dalwigk jo stimmt😅 hab mich verlesen, mein Fehler.
@@bruderalex89 ;)
Leider hast du den Distanzvektoralgorithmus nicht erklärt :(
Der war auch nicht Teil dieses Videos.
Hier geht es doch explizit um den Dijkstra Algorithmus!
@@Florian.Dalwigk Schon klar, ich mein ja nur dass du kein Video über diesen Algorithmus auf deinem Kanal hast ;)
Achso ... das habe ich bisher noch nicht produziert 😳
@@Florian.Dalwigk Na dann weißt du was zu tun ist :D Danke auf jeden Fall für deine Videos.
Naja dann gucke ich mal ob ich morgen ne 2 in Info schaffe😅
Vielleicht sogar eine 1? Viel Erfolg 🙂
Blob
?