(Floyd-)Warshall Algorithmus - Informatik (deutsch)
Вставка
- Опубліковано 13 жов 2024
- Lösung:
deprecated.blee...
-------------------------------------
hat dir eines meiner Videos geholfen?
Über etwas Unterstützung würde ich mich sehr freuen!
www.bleeptrack....
Wenn doch nur unser Prof so ausführlich erklären könnte... Danke dir!
So helpful I dont even need to understand german :-) danke
Gut gemacht. Ich habe nicht nur den Algoritmus gelernt, sondern auch ein Paar neuen Deutchen Wörter gelernt. Danke.
Děkuju. Jste z české republiky? Snažím se naučit česky v době :)
Ano, jsem z Česka :-) Držím Vám palce, ať se učení daří. Eine gute Sache für Ihres Ziel ist, das Tschechisch mit Deutsch beeinflusst ist. Obwohl die Wortschatz ist ziemlich verschieden, die Gramatik ist oft ähnlich (doch in der Regel mehr kompliziert).
mega Video, vielen Dank! hast meine Klausur gerettet ;D an der Uni wurde uns der Algo super kompliziert beigebracht, indem man immer den Graphen betrachtet und alle Wege von einem Konten zu einem anderen durchgeht, super langsam und fehleranfällig
Kleine Anmerkung: Wenn du neben die (Transport-)Kostenmatrix noch die Vorgängermatrix schreibst und entsprechend der Itertionen aktualisierst, kann man am Ende sehr gut nachvollziehen, welcher Weg hinter den entpsrechenden Einträgen der Kostenmatrix steht ohne, dass man auf den Graphen schauen muss.
Am Ende war dies leider nicht erklärt worden, aber genau diese Matrix fehlt noch. Die Transportmatrix Erklärung war super :-)
Sehr gutes Video aber eine Anmerkung habe ich noch: Der Floyd-Warshall-Algorithmus für APSP funktioniert auch für negative Kantengewichte solange es keine negativen Kreise gibt. Gibt es einen negativen Kreis, so kann der Floyd-Warshall-Algorithmus zumindest benutzt werden, die Existenz eines solchen zu verizieren.
Außerdem ist er mit einer Laufzeit von O(n^3) leider sehr Zeit intensiv.
Wer entschuldigt sich bitte für Katzen??? :)
Besser als die ganzen indischen Varianten :D Mein Info Prof hat dazu EINE Folie OHNE Beispiel gemacht. Keine Besprechung oder Übung und es dann eiskalt in der Klausur abgefragt.. Aller guten Dinge sind zwei und diesmal kann ich den Mist dann auch :D Dankeschön.
Ich drücke die die Daumen für deine Klausur 👍
Super Video, hat mir wirklich sehr geholfen ! Der Disma Prof hat mir damit davor ganzschön angst gemacht, aber ist ja eigentlich schon fast trivial wenn man es so sieht !
Nach 7 englischen videos endlich habe ich ein gutes gefunden. Obwohl ich bin nicht sehr gut in Deutsch, habe ich es verstanden!! Dankeschön
Endlich habe ich diesen Algorithmus verstanden. Ganz deutlich erklärt und klappt auch bei negativen Kantengewichte sowie undirected graph👋🏻🥰
Nach weniger als der Hälfte alles gecheckt, weil es so gut erklärt und veranschaulicht war aber bin für die Katzenbilder geblieben. Top video, danke dir;-)
Danke für die gute Erklärung! +süße Katze
Uii... cool du erklärst meinen Lieblingsalgorithmus. Hätte nie gedacht, das ich mal jemanden im Netz finde, der ihn so fancy aufmalt. Echt coole Sache und dickes Lob für deine Website. :)
Super erklärt. Die Aufgabe direkt beim ersten Versuch richtig gelöst, obwohl ich vorher in dem skript meines Profs nichts verstanden hab. Danke!!
Mareike Wichmann ich guck mir teilweise immer erst videos an und dann die skripte :D
I don't even know german well, and this video helped me a lot to understand this.
Ich danke dir!! Du hast das so einfach erklärt und mir Stunden von selber nachvollziehen erspart!!!!
Richtig tolles Video! Super schnell und richtig gut erklärt!
Habe mir verliebt in dein Kanal. Im Studium der absolute Retter :) Aber mal eine wichtigerer Frage, hast du nach 7 Jahren immer noch die Katze? :D
Ja, ist mittlerweile ein großer fetter Kater geworden :3 twitter.com/Bleeptrack/status/1097585650197585921
oh mein Gott was für eine Erklärung ist das, das war super hilfreich ich habe die Vorlesung zweimal gesehen und nicht verstanden und ein Video in 10 minuten verstanden
was ist, wenn eine negative zahl dabei ist, könnte sich eine null auf der diagonale dann verändern?
Schönes Video ! Echt gut erklärt.
Darf ich fragen welche Software Sie verwenden zum Anzeichnen?
MfG
+村上美子 Hi, das ist Sketchbook Pro. Mittlerweile benutzte ich allerdings Krita.
vielen vielen Dank🌸❤
Ich fange in eine Woche mein Informatik Studium an und nun versuche ich mich darauf vorzubereiten.
Ich habe alles verstanden und schreibe alles mit obwohl ich noch keine Ahnung habe in welchem Semester ich so was bekommen werde.
Vielleicht könntest du mir bitte sagen wann ich solche Algorithmus sehen werde und was ist mich jetzt am wichtigsten interessieren sollte ?
Vielen Dank im voraus
Hi, freut mich sehr, dass du dich für ein Informatikstudium entschieden hast. Vermutlich wirst du auf diesen Algorithmus im 2. Semester treffen. Wenn du dich schon vorher etwas einarbeiten willst, dann erkundige dich doch welche Programmiersprache du im ersten Semester lernen wirst und spiele damit ein bisschen herum. Das würde dir sicher den Einstieg erleichtern :)
Wow super Video, danke dafür, schreibe am Montag Algorithmen und Datenstrukturen und mein Dozent konnte es zwar erklären aber bei weitem nicht so gut und schnell verständlich machen wie du!
Wieder mal ein klasse Video. Studiere per Fernstudium und dein Videos helfen mir immer wieder beim verstehen der Lösungswege und Abläufe. Vielen Dank! :-)
vielen dank für die super erklärung und süße katze :)
Danke für die super Erkärung. Damit bist du bestimmt eine große Hilfe für viele Informatik Studenten ;)
Wenn ich in der Matrix dann was haben wie: (-3) + 2 --> Schreibe ich dann in die Matrix -1 oder 0?
Können die Werte in der Matrix also negativ werden?
Negative Werte in der Matrix sind zulässig. Prof hat im Skript eine Tabelle mit u.a auch negativen Werten drin.
Passt perfekt in meine Vorlesung!
Hey, ich glaube du hast einen kleinen Fehler in deiner Lösung...
Ich kann mich natürlich auch irren, aber müsste bei der Übungsaufgabe in der letzten Zeile, 2. Spalte nicht eine 5 statt der 6 stehen?
da 5 nach 2 : 5->3->2 = 3 + 2
Ansonsten super erklärt! :)
+GrafGold Hey, vielen Dank für deinen Hinweis. Das hast du sehr richtig erkannt. Ich habe es gerade nochmal nachgerechnet und die richtige Version in die Lösung gesetzt.
Sehr gutes und lehrreiches Video. Danke. Weiter so!
Hei Bleeptrack
ich habe eine Frage und zwar haben wir im Studium den Warshall Algorithmus nur an ungewichteten Graphen gemacht und alles andere mit 0 ausgefüllt - da die Matrix ja nun nur mit 1en und 0en aufgefüllt ist funktioniert das mit dem addieren ja nicht mehr so, wie muss ich das dann machen ? Ich hoffe du kannst mir helfen! Danke !
+Isi_en Wenn du einen ungewichteten Graphen hast, dann interessiert dich da nicht mehr der kürzeste Weg, sondern nur noch ob überhaupt ein Weg zwischen zwei Knoten existiert. Dabei kannst du praktisch genauso vorgehen: Beim Initialisieren der Matrix kannst du einfach eine 0 reinschreiben, wenn eine Verbindung besteht und ein unendlich, wenn keine besteht. Danach kannst du genau gleich vorgehen. Aus einem unendlich kann dann eben maximal eine Null werden. Das zeigt dir dann aber an, dass es zwischen diesen Knoten eben doch einen Weg gibt.
+Bleeptrack Dankeschön!
Deine Videos sind mega! Dankeschön :)
Weltklasse Video!
11:28 warum ist die 4 zur 1 so viel spannender als die 3 zur 4 (11:08)
müsste nicht eigentlich im ergebniss der weg 5 -> 2 10 sein? also in der matrix 5. zeile 2. spalte, wieso kommt da 11 raus?
11 sollte passen. Oben im Graph ist der kürzeste Weg von der 5 zur 2 5-3-1-2 mit Pfadlänge 11.
+Bleeptrack ah ja richtig, asche übermein haupt. habe die kante 3 zu 5 genommen anstannt 5 zu 3, danke für
die schnelle antwort!
+Bleeptrack noch eine andere frage: ich hab eine zusatzaufgabe, wie man die konkreten wege noch mittels des algorithmus angeben kann, so das man nur einen wert jeweils in der matrix extra speichert.
die frage: Zusatzaufgabe: Wie muss der Floyd-Warshall-Algorithmus modifiziert werden, um
nicht nur die L¨ange sondern auch die konkreten Wege zu erhalten. Wie kann man
die Wege dann ausgeben?
Hinweis: Es muss fur jedes Paar ( ¨ u, v) in der Matrix nur eine zus¨atzliche Information
gespeichert werden. Die Ausgabe erfolgt dann rekursiv.
weiß nich genau wie das gehen soll, vielen dank im vorraus
Hey, mein spontaner Vorschlag dazu wäre während dem Aufbauen der Matrix die Wege über die Knoten zu speichern. Z.b. in einer Liste. Also praktisch eine Matrix mit Listen. Das wäre dann aber mehr als nur eine Information. Wahrscheinlich reicht es dann einfach nur den Verweis zum nächsten Knoten zu speichern. Dann kann man immer an den Knotenverweisen entlang laufen und die so ausgeben :)
+Bleeptrack Ok vielen dank für die mühe! das klingt ganz gut ;)
Gutes Tutorial & süße Katzen
Wie heißt die software auf der du das ganze gemalt hast ?
HeaderGFX Sketchbook Pro. Mittlerweile benutze ich Krita.
danke, sehr hilfreich. Grüße aus berlin
Erstmal vielen Dank für das Video!
Ich hab aber noch eine Frage:
Was ist, wenn man negative Gewichtungen hat? - Dann wäre 0 ja nicht der kleinstmögliche Wert und müsste entsprechend auch beachtet werden, oder? Beim Floyd-Warshall Algorithmus dürfen soweit ich weiß ja auch negative Gewichtungen vorkommen...
Super hilfreich! Danke
Wirklich klasse erklärt! ICh habs auf Anhieb verstanden :) DANKE
Klasse video, dankeschön. viel besser als mein uniprof erklärt :)
stark gemacht, danke dir :)
Danke, hat mir sehr geholfen! :)
Ich hab hier eine Aufgabe mit negativen kantenwerten. Wie soll ich dann entscheiden wenn ich z.B -2 und 10 habe? Einfach ganz normal die -2 stehen lassen? Du sagtest ja man soll die kleineren Werte nehmen.
Ja, -2 ist kleiner als 10 und negative Werte sind zulässig.
sehr schön erklärt, danke!
Wirklich sehr gut erklaert. Weiter so
Danke, habs endlich verstanden :)
Du hast übrigens die Lösung falsch verlinkt, .../tutorials/warshall hat aber funktioniert :D
Sehr Gut!
Danke vielmals!
super erklärt, wie immer :)
suuuper, unser prof hat uns das leider so erklärt, dass man den graphen dann per hand abarbeiten muss und jeden verbindung des knotens zum ausgehenden knoten k dann abrechnet, was heißt, dass man bei jedem schritt jeden knoten durchrechnet ... das ist zwar machbar, wenn der graph klein ist aber bei größeren graphen mit mehr als 5 oder 6 knoten dauert das stunden. deine methode macht das binnen minuten!
Super erklärt! Dann mal ab ins examen :D
DANKE!!
Ich dachte man nimmt das Maximum oder ist das egal?? weil in der uni es so beigebracht wurde
ohhhhhh endlich verstanden danke
endlich gecheckt
Woher bekomme ich denn die Matrix?
Die kannst du aus dem Graph ablesen :) ich hab leider gerade keine Anleitung dazu zur Hand. Wenn du im Netz nix findest, dann hau mich nochmal an uns ich suche dir was raus.
@@bleeptrack Bin mittlerweile drauf gekommen :D mich hatten die ∞ irgendwie irritiert.. danke für deine Antwort!
Ich brauche den Algorithmus in meiner SQL Datenbank und bin durch dich gut in das Thema hineingekommen.
Der Link zur Lösung funktioniert nicht. Die Lösung findet man unter www.bleeptrack.de/tutorials/warshall
Gutes Video
Lasse ein Abo da ! :)
Gutes Video aber mein Like gilt zu 50% dem Kätzchen
Katzi :O
9:55 war gruselig.
man vertut sich so schnell in der matrix..
Wo sind die Katzenbilder xd
Danke!
Woa vielen Dank zurück!