- Aktuell
- In der Warteschlange
- Endgültig
- Weg
Dijkstra-Algorithmus
Der Dijkstra-Algorithmus findet den kürzesten Weg von einem Start zu jedem anderen Knoten, wenn die Kanten Längen haben, wie Straßen zwischen Orten. Er wächst vom Start aus nach außen und nimmt immer den nächstgelegenen Knoten, der noch nicht fertig ist. Klicken Sie auf einen Knoten, um dort zu starten, wählen Sie bei Bedarf ein Ziel, und gehen Sie Schritt für Schritt vor: Sie sehen die Warteschlange, wie jeder Abstand sinkt, sobald ein kürzerer Weg auftaucht, und wie der kürzeste Weg erscheint. Drücken Sie Abspielen, um der Suche zuzusehen, oder Schritt und Zurück, um Schritt für Schritt vorzugehen. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Klicken Sie auf einen Knoten, um ihn zum Start zu machen; stellen Sie den Klick auf Ziel um und klicken Sie auf einen anderen Knoten, um einen kürzesten Weg dorthin zu suchen. Die Zahl auf jeder Kante ist ihre Länge, die Zahl auf jedem Knoten sein bisher kürzester Abstand, und die Reihe unter dem Graphen ist die Warteschlange, die nächstgelegenen Knoten zuerst. Neuer Graph erzeugt einen anderen Graphen; wählen Sie, wie viele Knoten und Kanten er hat. Wenn das Feld ausgewählt ist, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.
Wie es funktioniert
- Klicken Sie auf einen Knoten, um ihn zum Start zu machen. Um einen Weg zu suchen, stellen Sie den Klick auf Ziel um und klicken Sie auf einen anderen Knoten.
- Drücken Sie Abspielen, oder gehen Sie mit Schritt und Zurück schrittweise vor. Ziehen Sie den Schrittregler, um an eine beliebige Stelle der Suche zu springen.
- Beobachten Sie die Warteschlange unter dem Graphen und den Abstand auf jedem Knoten. Neuer Graph erzeugt einen anderen Graphen zum Ausprobieren.
So funktioniert der Dijkstra-Algorithmus
Der Start bekommt den Abstand 0, jeder andere Knoten unendlich, und der Start kommt in eine Warteschlange. Dann wiederholt sich Folgendes: Der Knoten in der Warteschlange mit dem kleinsten Abstand wird genommen, und sein Abstand wird als endgültig markiert. Für jeden seiner Nachbarn, der nicht endgültig ist, wird die Länge der Kante zum Abstand des Knotens addiert. Ist die Summe kürzer als der bisherige Abstand des Nachbarn, wird sie sein neuer Abstand, der Knoten wird als Weg dorthin gemerkt, und der Nachbar kommt in die Warteschlange, falls er noch nicht darin war. Ist die Warteschlange leer, hat jeder erreichbare Knoten seinen kürzesten Abstand.
Warum der nächstgelegene Knoten endgültig ist
Ist ein Knoten der nächstgelegene in der Warteschlange, muss jeder andere Weg zu ihm den fertigen Teil des Graphen über einen Knoten in der Warteschlange verlassen, der mindestens genauso weit entfernt ist, und danach kommen nur Kanten hinzu, die nicht negativ sein können. Also kann kein anderer Weg kürzer sein. Darum ist ein Ziel auch erst sicher, wenn es aus der Warteschlange genommen wird, nicht schon, wenn es zum ersten Mal erreicht wird, und darum scheitert der Dijkstra-Algorithmus bei negativen Kanten: Dort braucht man den Bellman–Ford-Algorithmus. Hat jede Kante die Länge 1, macht der Dijkstra-Algorithmus dasselbe wie die Breitensuche.
Häufig gestellte Fragen
Was ist der Dijkstra-Algorithmus?
Ein Verfahren, das die kürzesten Wege von einem Startknoten zu allen anderen Knoten eines Graphen findet, dessen Kanten Längen von null oder mehr haben. Es nimmt immer wieder den nächstgelegenen unfertigen Knoten, macht seinen Abstand endgültig und verkürzt über seine Kanten die Abstände seiner Nachbarn.
Warum funktioniert der Dijkstra-Algorithmus nicht mit negativen Kanten?
Er macht den Abstand eines Knotens endgültig, sobald der Knoten der nächstgelegene in der Warteschlange ist. Eine später gefundene negative Kante könnte aber noch auf einem kürzeren Weg zu diesem Knoten zurückführen, sodass der endgültige Abstand falsch wäre. Der Bellman–Ford-Algorithmus kommt mit negativen Kanten zurecht, solange es keinen Zyklus mit negativer Summe gibt.
Was ist der Unterschied zwischen Dijkstra und BFS?
Die Breitensuche zählt Kanten und nutzt eine einfache Warteschlange. Der Dijkstra-Algorithmus addiert Kantenlängen und nutzt eine Prioritätswarteschlange, die immer den nächstgelegenen Knoten liefert. Hat jede Kante die Länge 1, finden beide dieselben Abstände.
Wie schnell ist der Dijkstra-Algorithmus?
Mit einem binären Heap als Prioritätswarteschlange wächst der Aufwand mit (V + E) log V bei V Knoten und E Kanten. Mit einem Fibonacci-Heap sind es E + V log V. Die App führt die Warteschlange als sortierte Liste, die sich leicht zeigen lässt und für kleine Graphen genügt.
Wird mein Graph irgendwohin gesendet?
Nein. Der Graph wird in Ihrem Browser erzeugt und durchsucht, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor