+lorenzl eins Freut mich. Fußnote: Wenn der Algorithmus schnell sein soll (und das muss er nur in der Praxis...) ist der Flaschenhals der, dass aus der Menge an unbesuchten Knoten schnell der mit der geringsten Distanz gefunden werden kann. Wenn man etwa die ganze Menge nach dem Minimum durchsucht, ist das nicht effizient - ideal ist da eine Vorrangwarteschlange, etwa über einen Heap.
ich hab jetzt mindestens drei verschiedene arten gefunden, wie leute den lösungsweg aufzeichnen, teilweise mit ner riesigen tabelle. die form hier ist die bisher kürzeste und einleuchtendste für mich, danke für das video!
Sauber erklärt. Setzt natürlich voraus dass der Graph als Knoten-Kanten-Modell aufbereitet ist. Es gibt auch noch Optimierungen davon, aber das führt womöglich zuweit hier.
Danke! Ist ein Graph nicht immer ein Knoten-Kanten-Modell? Der Laufzeit-Knackpunkt, den ich verschweige, ist das "suche nach dem unbesuchten Knoten mit der geringsten aktuellen Distanz", wo ein Heap sinnvoll wäre, aber diese Datenstruktur kennt man in der Schule nicht unbedingt.
als erstes: ich finde es super das es menschen gibt die solche vids machen! und das is das vid durch den ich den algo wirklich verstanden habe!! hab auch scho daumen nach oben gemacht =). danke. also nich falsch verstehen, aber ich glaube das irgendwas in deiner definition nich stimmt. nämlich erstens: wenn man den knoten mit geringster distanz sucht kann es auch vorkommen das in ihm noch unendlich steht (akt dist.) und wenn man was zu unendlich addiert -> nich so toll.
@bhbblblblllb Da ist das Missverständnis: die Distanz des aktuellen Knotens kann nie unendlich sein. Sie beginnt beim Startknoten mit 0, und der neue aktuelle Knoten (ermittelt in der Implementierung durch eine priority queue) ist (0+Kantengewicht), und so weiter. Ein Knoten wird ja erst dann aktuell gemacht, wenn seine Distanz eben nicht unendlich ist (sondern in der quee ganz vorne steht).
In der Regel nicht, dabei könnte man ja zum Beispiel einen zyklischen Pfad mit negativer Gesamtlänge haben, den man beliebig oft abgeht, wobei die Länge immer weiter schrumpft.
@Pagai Nein, die Frage "geringste Distanz zum aktuellen Knoten" taucht im Algorithmus gar nicht auf. Beim aktuellen Knoten geht es nur immer darum, alle noch nicht besuchten Nachbarn mal probeweise auszurechnen und eventuell zu aktualisieren - in welcher Reihenfolge man das macht, ist egal.
@HerrRau2 Wäre es möglich einmal Quicksort v die Rotation des AVL Baums von dir erklärt zu bekommen. Fand die Erklärung hier sehr schön simple gehalten. Weiter so !!
Ich weiß nicht, ob ich das richtig verstanden habe, biLo88. Es gibt feste Positionen (Waypoints) in der Spielwelt, und das Objekt kann nur jeweils von Position zu Position zu springen oder sich auf dem kürzesten direkten Weg dorthin begeben (was aufs gleiche hinausläuft). Dann wäre das wohl ein vollständiger Graph, so dass jede Position mit jeder anderen verbunden ist, und man soden kürzesten Weg findet. Aber das ginge dann wohl einfacher ohne Dijkstra. Oder gibt es doch feste Pfade/Kanten?
Das video ist schon hilfreich danke :) , aber eine Frage: Warum nimmst du nach dem Knoten B nicht den Knoten D sondern E ? Wie sollte man in dieser Situation den "unbesuchten Nachbarn" wählen, da B keine unbesuchten Nachbarn hat ?
Frage 2: Wenn es keine unbesuchten Nachbarn gibt, ist der Fall erledigt, man wählt gar keinen unbesuchten Nachbarn, sondern lässt diesen Schritt aus und überspringt ihn. Frage 1: Nach diesem Überspringen geht es regulär weiter, nicht mit irgendwelchen Nachbarn, sondern mit dem unbesuchten Knoten mit der geringsten Distanz - und das ist in diesem Fall nun mal E und nicht D. Was man leicht verwechselt: zuerst nimmt man den unbesuchten/unfertigen Knoten mit der geringsten Distanz, und danach bearbeitet man von dem aus alle unbesuchten Nachbarn (mit beliebiger Distanz, in beliebiger Reihenfolge).
Gewählt wird immer dann, wenn es um den unbesuchten Knoten mit der bislang geringsten Distanz geht. Wenn es da mehrere gibt, nimmt man irgendeinen davon. (Wenn es zwei gleich kürzeste Wege gibt, findet der Dijkstra dann entweder den einen oder den anderen; es kann ja nur einer herauskommen.)
@bhbblblblllb 2. wenn der ziel knoten noch einen knoten hat der ins leere fürt gibt es auch probleme. dann gehe ich vom ziel zu vorherigen -> der hat aber keinen vorgänger da er ja nur mim ziel verbunden ist!! bin mir nich sicher ob es stimmt glaube aber schon. arbeite atm an einer wegfindung und deshalb brauche ich es genau wie möglich. korrigiere mich wenn ich falsch liege... aber trozdem danke!!! super von dir...
Sehr nachvollziehbare Erklärung. Kleine Anmerkung dazu: Müsste es bei 6:30 nicht lauten "wird die 7 nicht eingetragen" statt "wird die 4 nicht eingetragen"?
schön erklärt, interessant wäre jetzt noch zu wissen wie ich jetzt zu den kürzesten Weg zum Knoten finde. Bringt mir ja nix, wenn ich weiß das der kürzeste Weg nach Berlin ist 500 km ist, nur welcher Weg das ist weiß ich nicht.
@bhbblblblllb Nein, das stimmt schon. Es ja nie etwas zu unendlich addiert, sondern nur die Summe von (Distanz des aktuellen Knotens + Kantengewicht) mit der Distanz der Nachbarknoten *verglichen*, die durchaus unendlich sein kann. Dann wird der unendlich Wert ersetzt durch den neuen, nicht dazu addiert.
Erst mal danke für dieses Video. Ich habe die Basis wissen mit einmaligen ansehen verstanden, aber dennoch habe ich eine Frage dazu. Wie ist das, wenn man die Vorgänger gar nicht kennt. Ich arbeite mit Waypoints in einem Spiel und da ist es schwer zu ermitteln welches davon der Vorgänger ist. In diesem Video wird erklärt Vorgänger der C ist B (Laut Buchstaben ja ^^), aber guckt man die Linien an ist C mit A auch verbinden. Wieso kann dann A nicht Vorgänger von C sein.
@MrAustraliarules Ist zumindest denkbar, AVL habe ich mal angerissen (aber ohne Erklärung des Algorithmus), Quicksort mache ich sicher mal irgendwas. Mal.
Oh, ich merke gerade, dass ich mich total Falsch ausgedrückt habe. Es geht eher um die Nachbarn. Ich setze Positionen in der Spielewelt ein. Z.b. (10,10,0) und ein anderer Punkt ist (10,15,0) noch einer (5,5,0) usw. Da gibst also keine Nachbarn (weil es uach noch keine Kollisionen gibt nur das man nicht runterfallen kann. Klippen usw.). Was ich mindestens machen kann, das mein Objekt sich über die Wegpunkte entlang bewegen kann (oder in der Nähe). Naja ein schwieriges Thema für mich denke ich.
@HerrRau2 ja aber wenn: (Distanz des aktuellen Knotens + Kantengewicht) zutrifft und Distanz des aktuellen Knotens = unedlich ist hat man das problem. und das kommt durchaus vor bei der definition wie du sie gegeben hast. wahrscheinlich weist du es schon aber man sollte die offnen knoten in eine priority queue tun... dann kann es nich passieren das man einen knoten hat bei dem die distanz des aktuellen knotens unendlich ist. vorallem wir die distanz dieses knoten auch nich mehr geändert...
Ich denke, Generic Label Correcting Algorithm ist ein Oberbegriff, unter den auch Dijkstra fällt. Jetzt wären natürlich Beispiele schön... aber die kann ich nicht liefern.
also ich hab hier überhaupt nichts kapiert...lt meinen aufgaben soll ich auch einen kürzesten weg finden aber bei meinen knoten stehen schon zahlen drin.. ich kapier schon garnich wie du das rechnest, oder wie man da anfängt oder
@bhbblblblllb Das stimmt wohl auch nicht. Ich weiß nicht genau, was du mit Zielknoten oder ins Leere meinst, aber der Algorithmus dürfte so schon stimmen.
Richtig, es geht immer um die aktuell kürzeste Distanz vom Ausgangsknoten A. Und nachdem B erledigt ist, ist der am schnellsten von A aus erreichbare Knoten E, deshalb geht es mit dem weiter.
oh man ich krieg schon vor dem richtigen Anfang die Krise, weil du so oft das Gleiche sagst.. das ist echt ziemlich anstrengend und zieht das eigentlich gute Video unfassbar in die Länge.
![รวมเพลงลูกทุ่ง 6 หนุ่มไทบ้าน ฮิตติดกระแส ชุดที่ 1 l มนต์แคน ไมค์ ไผ่ เสถียร ไหมไทย พี [Longplay]](http://i.ytimg.com/vi/GD2v1OjMw5I/mqdefault.jpg)
DANKE!!! hab anhand dieser angaben mein Algorithmus geschrieben. Funktioniert perfekt!!! DANKE!
+lorenzl eins Freut mich. Fußnote: Wenn der Algorithmus schnell sein soll (und das muss er nur in der Praxis...) ist der Flaschenhals der, dass aus der Menge an unbesuchten Knoten schnell der mit der geringsten Distanz gefunden werden kann. Wenn man etwa die ganze Menge nach dem Minimum durchsucht, ist das nicht effizient - ideal ist da eine Vorrangwarteschlange, etwa über einen Heap.
Sehr Nice, danke hat mir das ganze wudnerbarerklärt
ich hab jetzt mindestens drei verschiedene arten gefunden, wie leute den lösungsweg aufzeichnen, teilweise mit ner riesigen tabelle. die form hier ist die bisher kürzeste und einleuchtendste für mich, danke für das video!
Weltklasse - danke! :)
Bestes Tutorial für Dijkstra. Dankeschön!
Dominik Bünzli Bitteschön!
Da war ich in der Vorlesung wohl kurz geistig abwesend... Jetzt hab ichs trotzdem verstanden, danke! :)
Bitteschön, gern geschehen.
Danke für die gute Erklärung! Hat mir sehr geholfen :)
Danke hat sehr geholfen !
Danke für die übersichtliche und nachvollziehbare Erklärung!
Daumen hoch von mir :)
Gern geschehen!
old, but gold. Gute Erklärung
danke fuer das schoene video :)
Super Video !
Hilft super für die Abiprüfung im Info-LK !
Dankeschön !
Jederzeit wieder. Wenn ich mal wieder dazu komme.
Beste Erklärung, die ich im Netz finden konnte, Top!
Vielen Dank!!!
Danke!
Hat mir geholfen den Algorithmus endlich zu verstehen und meine java-Umsetzung ist hiernach euch schon recht weit.
Freut mich.
Sehr, sehr gut erklärt!
Kam bei mir in der Prüfung dran
2,0 bekommen in Algorithmen und Datenstruktur
Danke für die gute Erklärung
Gern geschehen, freut mich.
Sauber erklärt. Setzt natürlich voraus dass der Graph als Knoten-Kanten-Modell aufbereitet ist. Es gibt auch noch Optimierungen davon, aber das führt womöglich zuweit hier.
Danke! Ist ein Graph nicht immer ein Knoten-Kanten-Modell? Der Laufzeit-Knackpunkt, den ich verschweige, ist das "suche nach dem unbesuchten Knoten mit der geringsten aktuellen Distanz", wo ein Heap sinnvoll wäre, aber diese Datenstruktur kennt man in der Schule nicht unbedingt.
Super gewähltes Beispiel und sehr gut erklärt. Endlich habs ich auch verstanden :>
als erstes: ich finde es super das es menschen gibt die solche vids machen! und das is das vid durch den ich den algo wirklich verstanden habe!! hab auch scho daumen nach oben gemacht =). danke.
also nich falsch verstehen, aber ich glaube das irgendwas in deiner definition nich stimmt. nämlich erstens:
wenn man den knoten mit geringster distanz sucht kann es auch vorkommen das in ihm noch unendlich steht (akt dist.) und wenn man was zu unendlich addiert -> nich so toll.
Toll erklärt, vielen Dank!
Gern geschehen, freut mich.
Nicht schlecht, danke ;)
Besten Dank!!!!
Super erklärt ich hab's verstanden!!!
Gern geschehen.
Hat mir sehr geholfen, dankeschön! :)
Um... freut mich.
Gut erklärt. Gut wäre eine Anschauung mit gewichteten graphen, da dies häufiger auftaucht!
Find das Video echt gut!
Gut erklärt, aber welchen Knoten muss ich wählen wenn 2 oder mehrer Distanzen die selbe Länge haben und den kürzesten Weg darstellen?
top!
@bhbblblblllb Da ist das Missverständnis: die Distanz des aktuellen Knotens kann nie unendlich sein. Sie beginnt beim Startknoten mit 0, und der neue aktuelle Knoten (ermittelt in der Implementierung durch eine priority queue) ist (0+Kantengewicht), und so weiter. Ein Knoten wird ja erst dann aktuell gemacht, wenn seine Distanz eben nicht unendlich ist (sondern in der quee ganz vorne steht).
Hallo, danke für das Video.
Geht das auch für negative Kanten?
In der Regel nicht, dabei könnte man ja zum Beispiel einen zyklischen Pfad mit negativer Gesamtlänge haben, den man beliebig oft abgeht, wobei die Länge immer weiter schrumpft.
@Pagai Nein, die Frage "geringste Distanz zum aktuellen Knoten" taucht im Algorithmus gar nicht auf. Beim aktuellen Knoten geht es nur immer darum, alle noch nicht besuchten Nachbarn mal probeweise auszurechnen und eventuell zu aktualisieren - in welcher Reihenfolge man das macht, ist egal.
Danke ich lerne das fürs abi:) Info mündlich
info abi ballert
mit welchem programm wurden die zeichnungen angefertigt ?
@HerrRau2 Wäre es möglich einmal Quicksort v die Rotation des AVL Baums von dir erklärt zu bekommen.
Fand die Erklärung hier sehr schön simple gehalten. Weiter so !!
Ich weiß nicht, ob ich das richtig verstanden habe, biLo88. Es gibt feste Positionen (Waypoints) in der Spielwelt, und das Objekt kann nur jeweils von Position zu Position zu springen oder sich auf dem kürzesten direkten Weg dorthin begeben (was aufs gleiche hinausläuft). Dann wäre das wohl ein vollständiger Graph, so dass jede Position mit jeder anderen verbunden ist, und man soden kürzesten Weg findet. Aber das ginge dann wohl einfacher ohne Dijkstra. Oder gibt es doch feste Pfade/Kanten?
Das video ist schon hilfreich danke :) , aber eine Frage:
Warum nimmst du nach dem Knoten B nicht den Knoten D sondern E ?
Wie sollte man in dieser Situation den "unbesuchten Nachbarn" wählen, da B keine unbesuchten Nachbarn hat ?
Frage 2: Wenn es keine unbesuchten Nachbarn gibt, ist der Fall erledigt, man wählt gar keinen unbesuchten Nachbarn, sondern lässt diesen Schritt aus und überspringt ihn.
Frage 1: Nach diesem Überspringen geht es regulär weiter, nicht mit irgendwelchen Nachbarn, sondern mit dem unbesuchten Knoten mit der geringsten Distanz - und das ist in diesem Fall nun mal E und nicht D.
Was man leicht verwechselt: zuerst nimmt man den unbesuchten/unfertigen Knoten mit der geringsten Distanz, und danach bearbeitet man von dem aus alle unbesuchten Nachbarn (mit beliebiger Distanz, in beliebiger Reihenfolge).
Thomas Rau hab verstanden danke nochmals . .
Gewählt wird immer dann, wenn es um den unbesuchten Knoten mit der bislang geringsten Distanz geht. Wenn es da mehrere gibt, nimmt man irgendeinen davon. (Wenn es zwei gleich kürzeste Wege gibt, findet der Dijkstra dann entweder den einen oder den anderen; es kann ja nur einer herauskommen.)
@bhbblblblllb
2. wenn der ziel knoten noch einen knoten hat der ins leere fürt gibt es auch probleme. dann gehe ich vom ziel zu vorherigen -> der hat aber keinen vorgänger da er ja nur mim ziel verbunden ist!! bin mir nich sicher ob es stimmt glaube aber schon.
arbeite atm an einer wegfindung und deshalb brauche ich es genau wie möglich. korrigiere mich wenn ich falsch liege...
aber trozdem danke!!! super von dir...
Sehr nachvollziehbare Erklärung. Kleine Anmerkung dazu: Müsste es bei 6:30 nicht lauten "wird die 7 nicht eingetragen" statt "wird die 4 nicht eingetragen"?
Tolator Stimmt! Zum Glück spreche ich so schnell und undeutlich, dass man das nicht so groß merkt... Danke!
nice
hätte Knoten D nicht vor Knoten E kommen müssen? wg. der geringsten Distanz zum aktuellen Knoten?
schön erklärt, interessant wäre jetzt noch zu wissen wie ich jetzt zu den kürzesten Weg zum Knoten finde. Bringt mir ja nix, wenn ich weiß das der kürzeste Weg nach Berlin ist 500 km ist, nur welcher Weg das ist weiß ich nicht.
Das ist mit Libre Office gemacht, eine Präsentation mit Zeichnungsobjekten darin.
@bhbblblblllb Nein, das stimmt schon. Es ja nie etwas zu unendlich addiert, sondern nur die Summe von (Distanz des aktuellen Knotens + Kantengewicht) mit der Distanz der Nachbarknoten *verglichen*, die durchaus unendlich sein kann. Dann wird der unendlich Wert ersetzt durch den neuen, nicht dazu addiert.
Erst mal danke für dieses Video. Ich habe die Basis wissen mit einmaligen ansehen verstanden, aber dennoch habe ich eine Frage dazu. Wie ist das, wenn man die Vorgänger gar nicht kennt. Ich arbeite mit Waypoints in einem Spiel und da ist es schwer zu ermitteln welches davon der Vorgänger ist. In diesem Video wird erklärt Vorgänger der C ist B (Laut Buchstaben ja ^^), aber guckt man die Linien an ist C mit A auch verbinden. Wieso kann dann A nicht Vorgänger von C sein.
@MrAustraliarules Ist zumindest denkbar, AVL habe ich mal angerissen (aber ohne Erklärung des Algorithmus), Quicksort mache ich sicher mal irgendwas. Mal.
Schöne erklärung
gibt es auch ein video auf deutsch, dass den kürzesten weg allen knoten zu allen knoten zeigt??
Ja, Dijkstra funktioniert generell nur bei positiven Werten.
gute illustration!
Oh, ich merke gerade, dass ich mich total Falsch ausgedrückt habe. Es geht eher um die Nachbarn. Ich setze Positionen in der Spielewelt ein. Z.b. (10,10,0) und ein anderer Punkt ist (10,15,0) noch einer (5,5,0) usw. Da gibst also keine Nachbarn (weil es uach noch keine Kollisionen gibt nur das man nicht runterfallen kann. Klippen usw.). Was ich mindestens machen kann, das mein Objekt sich über die Wegpunkte entlang bewegen kann (oder in der Nähe). Naja ein schwieriges Thema für mich denke ich.
@HerrRau2
ja aber wenn: (Distanz des aktuellen Knotens + Kantengewicht) zutrifft und Distanz des aktuellen Knotens = unedlich ist hat man das problem. und das kommt durchaus vor bei der definition wie du sie gegeben hast. wahrscheinlich weist du es schon aber man sollte die offnen knoten in eine priority queue tun... dann kann es nich passieren das man einen knoten hat bei dem die distanz des aktuellen knotens unendlich ist. vorallem wir die distanz dieses knoten auch nich mehr geändert...
Ich denke, Generic Label Correcting Algorithm ist ein Oberbegriff, unter den auch Dijkstra fällt. Jetzt wären natürlich Beispiele schön... aber die kann ich nicht liefern.
Bzw. hat alles Nachbarn wollte ich noch hinzufügen
also ich hab hier überhaupt nichts kapiert...lt meinen aufgaben soll ich auch einen kürzesten weg finden aber bei meinen knoten stehen schon zahlen drin..
ich kapier schon garnich wie du das rechnest, oder wie man da anfängt oder
@HerrRau2
dann passt es =)
@bhbblblblllb Das stimmt wohl auch nicht. Ich weiß nicht genau, was du mit Zielknoten oder ins Leere meinst, aber der Algorithmus dürfte so schon stimmen.
@ratona14100 Wenn's mal in der Schule drankommt (oder ich das als Referat verteilen kann), gerne. Sieht aber erst mal nicht so wahrscheinlich aus.
Nach B könnte ich zu D von C...das ist viel weniger als E. Oder?
Also, E soll gewählt werden, da es von Vorgänger A mit Distanz 4.
Richtig, es geht immer um die aktuell kürzeste Distanz vom Ausgangsknoten A. Und nachdem B erledigt ist, ist der am schnellsten von A aus erreichbare Knoten E, deshalb geht es mit dem weiter.
boah ich krieg echt nen hals wenn ich mir das anschau. Das ist echt für begriffsstuzige oder...
oh man ich krieg schon vor dem richtigen Anfang die Krise, weil du so oft das Gleiche sagst.. das ist echt ziemlich anstrengend und zieht das eigentlich gute Video unfassbar in die Länge.
sehr schlecht erklärt!!!
Labber