Dijkstra-Algorithmus
HTML-код
- Опубликовано: 8 сен 2024
- In diesem Video präsentiert Prof. Dr. Oliver Lazar den Dijkstra-Algorithmus aus der Gruppe der Graphalgorithmen. Der Algorithmus berechnet die kürzesten Distanzen von einem Knoten zu allen anderen. Mit Hilfe eines Beispiels wird der Ablauf Schritt für Schritt nachvollziehbar erläutert.
Hey yo, hab die Klausur vor 1,5 Jahren dank dir bestanden und steh vorm Bachelor. Beste Videos die es gibt!
Nach 2 Stunden vergebens auf dieses Video gestoßen und sofort verstanden! Ehrenmann!
Wow perfekt! Vielen dank für die tolle Erklärung. Ich brauchte das dringend für meine Hausaufgaben.
You prolly dont give a shit but does any of you know a tool to log back into an Instagram account?
I was stupid lost my login password. I appreciate any tips you can give me
@Randall Sam instablaster :)
@@isaaccesar8486 *SCAM*
Super Video klasse das du alles mit Beispielen näher bringst echt toll
Ich weiß, dass das schon mehrere gesagt haben, aber eines fehlt. Du hast es so gut und so verständlich erklärt, dass ich es nicht nur verstanden, sondern GELERNT habe. Du hast alles wichtige gesagt:
- Es werden ALLE Punkte erreicht
- Sind zwei gleich gewichtet, nehme ich den, der für mich attraktiver ist
Zu, Beispiel: Sind die Knotenpunkte Restaurants, nehme ich den Punkt, bei dem ich sehr viel Menschenverkehr habe
Super...TOLLE LEISTUNG
Danke schön im Deteil erklärt und nicht so durchgerusht wie das sonst so oft der Fall ist
Very informative. You are doing a great job.
Super easy erklärt, sogar viel besser zu verstehen als aus Sedgewick "Algorithms ..". Vielen Dank!
Wie kann man die Besuchsreihenfolge D -> B interpretieren? Da ist zwischen D und B keine Kante.
Du hast auf jeden Fall 1000 Likes verdient. Dank dir hab ich diesen Dijkstra Algorithmus innerhalb von 12 Minuten endlich verstanden. Wirklich vielen vielen Dank. Eine Frage, hast du auch Videos zu den Analysis Themen? Wäre dir sehr Dankbar
Danke, Sehr gut erklärt.
Richtige Ehrenmann 👍
Anmerkungen:
1) Die wichtigste Frage nach dem kürzesten Pfad wird nicht beantwortet (nur Distanz "27" - aber über welche Knoten??). Die Besuchsreihenfolge entspricht nicht dem kürzesten Pfad (kann man schon daran sehen das z. B. B und F nicht Teil des kürzesten Pfades sein können, da sie keine abgehenden Kanten haben)
2) Ich kann nicht erkennen, welches Kriterium zum "abhaken" eines Knotens führt (die roten Punkte im Tabellenkopf)?
3) Das "Durchziehen" eines Wertes ans Ende der Tabelle wird nicht erklärt: Grund ist, dass z. B. bei "E" alle eingehenden Kanten (A -> E) betrachtet wurden und somit kein kürzerer Weg existieren kann
Sehr gutes Video, danke für die Erklärung.
- Wirtschaftsinformatik Student
Super Video, in 12min besser eklärt als der Prof. in einer Stunde
Danke für die Erklärung!
Wie würde man jetzt mit der Tabelle den kürzesten Weg von bspw. A zu H ermitteln ?
10:22 Selbst wenn G jetzt B erreichen kann, ist ja B bereits als "besucht" markiert. Dann muss man doch B überhaupt nicht mehr betrachten. Oder können sich denn die Kosten für B ändern auch wenn es bereits besucht wurde?
Ist das ein normaler Algorithmus oder der neue Avengers Film
Danke, echt gutes Video ^^
Irgendwie finde ich, dass das Video nicht die ganze Problematik erklärt? Es ist hiernach bereits klar, wie die Tabelle dann aussieht, wie ich den Weg von A nach H nehme und welche Knoten hierfür genommen werden müssen um die kürzeste Strecke zu kriegen, wird nicht so ganz klar?
Wie sieht es dann mit anderen Punkten aus? Wenn ich als Startknoten z.B. den C habe ? Hierfür muss doch dann auch eine Tabelle erstellt werden oder ?
Da muss ich mir bei jedem Knoten doch auch die vorherigen Punkte irgendwo merken um dann von der Tabelle richtig ablesen zu können wo ich eigentlich lang muss?
Sehr hilfreich danke
Danke! Sehr gut erklärt.
Also bestimmt man mit dem Dijkstra Algorithmus nicht die Kosten von einem Anfangspunkt zu einem bestimmten Endpunkt, sondern die geringsten Kosten um einen x-beliebigen Punkt zu erreichen?
Wie kann man sich sicher sein, dass sich die Kosten nicht mehr ändern ? Du hast relativ random immer entschieden ob du bist unten direkt durchschreibst
Eine kurze Frage zu dem Initial Schritt.
Ich habe in manchen Vorlesungsfolien gelesen, dass man, anstatt gleich die markierten Knoten mit seinen Werte aufschreibt, zuerst die Knoten mit Unendlich setzt. Wären es dann nicht am Ende n = 8 Schritte?
Danke für deine Antwort im voraus
Wenn dir das lieber ist, dann mach doch diesen ersten Schritt noch dazu. Das ändert ja nichts am Gesamtablauf und dem Algorithmus selbst.
Wenn jetzt A -> F 2 wäre, dann hätte man das als 1ste bzw. 2ste Iterationen nehmen müssen? Das heißt die nächste Iteration ist nicht inmer unbedingt ein Nachbarknoten oder ? :-)
intro gibt helldivers 2 vibes FOR SUPER EARTH
leider nicht ganz richtig ! Der Weg direkt von E zu B zu springen ist falsch. Der Algorithmus würde an dieser Stelle zuerst zu D springen da dieser Knoten am kürzesten(schnellsten) von E zu erreichen ist.
ich liebe dich
video ist mir leider nicht klar bei dem b kann man zu der H gehen und es wird 10 von b plus 2 von der h gleich 12 oder wie ?
Kann man nicht, es gibt einen Weg von H zu B aber nicht von B zu H, die Wege sind gerichtet und können nicht in beide Richtungen verwendet werden.
@@Hexadris Die Methode funktioniert allerdings auch bei ungerichteten Wegen - man muss das nur während der Anwendung mit bedenken.
Worin unterscheidet sich der Dijkstra- vom Prim-Algorithmus?
Dijkstra berechnet die kürzesten Wege von einem bestimmten Knoten zu allen anderen, das ist dann nicht unbedingt der minimale Spannbaum! Den minimalen Spannbaum berechnet der Prim-Algorithmus. Das ist ein Baum ohne redundante Wege mit minimalen Kosten.
Vielen Dank für die schnelle Antwort! Und wenn ich noch weiter fragen dürfte, könnte man die Aussage treffen, dass der Prim-Algorithmus lediglich bei einem *ungerichteten* Graphen einen minimalen Spannbaum liefert? Oder ist das auch bei einem *gerichteten* Graphen der Fall? Oder hat das keine Relevanz?
Und ferner, ohne es zuvor überprüft zu haben, ist der Prim-Algorithmus gegenüber dem Kruskal-Algorithmus effizienter und schneller?
How you go to D to B and B to C , no way this path. if you use same point way, this length is wrong.. ????
Correct. D is an "end only" node in this network. Same goes for B.
The method, however, works the exact same in networks where you can travel in both directions along the edges. You just need to account for that if you try to determine which other points are reachable.
Super ALgorythmus
Im Video klingt es so, als könnte man mit dem Djikstra auch minimale Spannbäume bestimmen.
Dijkstra ist soweit richtig ausgeführt, der minimale Spannbaum ist dies aber nicht!
Benutze die Kante H->B , anstatt von E->B und ich habe einen Spannbaum, der 6 weniger Einheiten kostet.
Hallo Marvin812, ich habe jetzt noch einmal genau nachgeschaut und der Dijkstra berechnet die kürzsten Wege von einem Knoten zu allen anderen. Du hast Recht, dass dies nicht der minimale Spannbaum sein muss. Den minimalen Spannbaum berechnet der Prim-Dijkstra-Algorithmus. Mea culpa. Grüße
Also die Standartdefinition, die ich kenne:
Ein Spannbaum ist ein zusammenhängender Teilgraph des UNGERICHTETEN Graphens G, der alle Knotenüberdeckt von G überdeckt.
Das Gewicht eines Graphens(also auch eines Spannbaumes) ist gleich der Summe der Kantengewichte.
Zunächst einmal: Auf welche Definition eines Spannbaumes beziehst du dich hier? Vorallem,weil wir hier einen gerichteten Graphen haben.
Ich glaube das, was du als Spannbaum beschreibst geht eher so in die Richtung eines Entfernungsbaumes(auf diesen Begriff bin ich vereinzelnt getroffen).
Wobei Prim auch nur in ungerichteten Graphen funktioniert. In gerichteten Graphen gibts es wie bereits erwähnt keine minimalen Spannbäume.
Es wäre super, wenn du im Video an dieser Stelle eine Anmerkung setzt, damit niemand auf den falschen Weg geleitet wird.
Irgendwie verstehe ich das nicht. Ja klar kleinster Wert für die Kantengewichte aber man kommt doch gar nicht von beispielsweise D zu B wieso ist das dann der kürzeste weg wenn ich die knoten nicht erreiche
Es wird beim Dijkstra immer ein Startknoten definiert und es gilt, die kürzesten Wege von diesem Startknoten aus zu allen anderen Knoten zu finden (im Beispiel ist das der Knoten A).
Du musst dir immer A als deinen Startknoten vorstellen. Kommt ein weiterer hinzu, z.B. E, ist das einer neuer Knoten von wo du agieren kannst.
Von D zu B gibt es keinen Weg. Aber du kannst von A nach E und dann nach B. Und das dann für 2+8 Kosten.
Holy dieses intro
Der Jungster Professor ich gesehe habe
supi
Gut erklärt, allerdings finde ich persönlich die Tabelle sinnlos, da man die Werte (kürzesten Wege) direkt miteinander verrechnen kann.
Aber nicht dein Programm
Wieso kannst du direkt sagen, dass E abgeschlossen ist am Anfang? Oder auch D, was ist wenn es mehr wege gibt nach D? Ich würde sagen dass kann man erst sagen, wenn es keine eingehenden Kanten mehr gibt zu einem Knoten
Nein, das ist absolut korrekt so, genau so wird es beispielsweise auch in den Vorlesungen zur theoretischen Informatik vermittelt.
Es gibt keine Möglichkeit, dass man E billiger erreichen kann, denn jeder andere Weg, der von A weg geht, hat definitiv höhere Kosten.
Warum sind alle Graphen zu diesem Thema nicht maßstabgerecht ? Warum ist die Strecke A-E länger als A-D und kürzer gezeichnet ? Das hilft mir nicht, das Problem zu verstehen.
Das Problem bei deinem Verständnis liegt darin, dass du dir mit der Kantenbewertung offensichtlich eine Distanz assoziierst. Der Wert an der Kante kann aber im Prinzip für ganz viele Dinge stehen, z.B. die mittlere Warteschlangenzeit für ein Testpaket in einem Netzwerk, die Kapazität eines Rohres und vieles mehr. Eine Kante ist kein Vektor, die Länge der Kante in der Zeichnung ist letztendlich irrelevant, schau nur auf den Wert daran.
Durch nicht maßstabgerechte Darstellung wird es unanschaulich. Wozu dann unterschiedliche Werte und der Algorthmus, wenn es letztlich egal ist ?
@@FirstLast-hm8oz Du verstehst meine Erläuterung nicht!!! Denke nicht so eindimensional! Wer behauptet denn, dass der Wert an der Kante eine Distanz ist? Es kann doch auch der Durchmesser sein und es geht dann um eine mögliche Durchflussmenge. Ich kann ja nichts dafür, wenn du es dir unbedingt ausschließlich als räumliche Distanz vorstellst.
Es ist meistens auch beabsichtigt, dass diese Kantenlängen nicht mit Ihren Wert in Relation stehen. Damit versuchen die Zeichner den Gedankengang , die Länge der Kanten mit ihren Werten zu assoziieren, zu unterbinden!
@First Last Sorry aber entweder trollst du gerade heftig oder die Mathematik ist überhaupt nicht deine Stärke, denn es geht hier nicht um maßstabgerechte Darstellung, sondern darum, dass du die Vorgehensweise des Algorithmus verstehst anhand einer Skizze. Nur weil es nicht maßstabgerecht ist, kannst du doch nicht schlussfolgern, dass der Algorithmus und die Gewichtung der Kanten unbrauchbar sind? Es geht hier nicht um Belanglosigkeiten, wie maßstabgerechte Darstellung, sondern darum, die Vorgehensweise des Algorithmus zu verstehen. Wenn du Volumen von einem Würfel berechnest, da zeichnest du ja auch nicht den Würfel maßstabgerecht in dein Heft. Ich verstehe dein Problem nicht.