Zum Inhalt springen
L

Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).

Der Dijkstra-Algorithmus

Institut für Bauinformatik - TU Dresden6:28 1.977 Aufrufe veröffentlicht Auf YouTube

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

Transkriptautomatisch erstellt · 48 Zeilen
Herunterladen
  1. Der Dijkstra-Algorithmus wird angewandt, um für einen Graphen den kürzesten Weg zu finden. Klassischer Anwendungsfall ist die Suche nach dem schnellsten Weg über verschiedene Straßen.
  2. Es gibt dabei eine Reihe von Knoten und diese sind durch Kanten miteinander verbunden. Das Gewicht einer Kante gibt z.B. an, wie hoch die Kosten für die Verbindung sind oder
  3. wie lange es dauert, von einem zum anderen Knoten zu gelangen. Der Dijkstra-Algorithmus geht von einem Startknoten aus und ermittelt für jeden anderen Knoten
  4. den kürzesten Weg zu diesem. Im einfachsten Fall kennt der Startknoten nur eine Kante und diese führt direkt zum
  5. Ziel. Etwas schwieriger wird die Suche bei mehreren Stationen.
  6. Vom Startknoten wird sich für den kürzesten Weg entschieden und in der Instanz vom zweiten Knoten zwischengespeichert, dass sie 13 Einheiten vom ersten entfernt ist.
  7. Von dort wird dann weiter gesucht und schließlich der letzte Knoten gefunden. Dieser ist dann 8 + die zwischengespeicherten 13 vom Startknoten entfernt.
  8. Es wird außerdem vermerkt, welcher Knoten auf dem Weg zum Startknoten genommen wurde, sodass der Weg zurückverfolgt werden kann.
  9. Dies ist wichtig, da es wie im nächsten Beispiel mehrere Wege zum Ziel gegeben kann und gespeichert werden muss, welcher der günstigste ist.
  10. Begonnen wird wieder links mit dem Startknoten und von diesem geht eine Kante mit dem Gewicht 13 aus.
  11. Es wird also als Distanz für den Knoten die 13 gespeichert und als Vorgänger der Startknoten angegeben.
  12. Außerdem geht vom Startknoten noch eine zweite Kante mit dem Gewicht 20 aus. Der rechte Zielknoten ist bisher noch unentdeckt und hat deshalb vorrübergehend den Wert „unendlich“.
  13. Der Startknoten kann dann als erledigt markiert werden, da alle Verbindungen, die von ihm ausgehen, überprüft wurden.
  14. Aus den orangenen Knoten wird dann mit dem Knoten fortgefahren, der die geringste Distanz aufweist, also dem Knoten mit der 13.
  15. Er kennt insgesamt 3 Kanten. Einmal den Weg zurück zum Startknoten, welcher jedoch als erledigt markiert wurde und deshalb
  16. nicht weiter beachtet werden muss. Dann folgt eine Verbindung zum Zielknoten mit dem Gewicht 11, sodass sich als Gesamtdistanz
  17. für ihn 24 ergibt. Schließlich noch eine günstige Verbindung nach unten, welche 6 Einheiten kostet.
  18. Mit 13+6 ist der Weg damit um 1 kürzer als die bisher bekannte Route. Aus diesem Grund wird der Wert für die Distanz aktualisiert und auch der Vorgänger umgeändert.
  19. Damit sind alle Verbindungen des oberen Knoten durchsucht worden und er kann als abgeschlossen markiert werden.
  20. Aus den orangenen Knoten wird als nächstes wieder der kleinste ausgewählt, das ist dieses Mal die 19.
  21. Die ersten beiden Kanten führen zu als erledigt markierten Knoten, für die bereits der optimale Wert ermittelt wurde, aber die letzte Kante ist noch offen.
  22. Auch hier ist der neue Weg wieder um 1 kürzer als die bisher gefundenen 24 und so wird die Distanz und der Wert für den Vorgänger ein letztes Mal aktualisiert.
  23. Zum Schluss sind dann alle Knoten als erledigt markiert und kennen ihre optimale Distanz zum Startknoten.
  24. Bisher hätte man das noch einfach durch bloßes Raufschauen schnell erkennen können, aber im nächsten Beispiel ist die Lage nicht ganz so offensichtlich.
  25. Wir beginnen mit dem Startknoten oben links und es werden drei Kanten identifiziert, welche orange markiert werden.
  26. Der Startknoten ist damit abgearbeitet und es geht weiter mit dem kleinsten Wert, der 7.
  27. Sie findet einen neuen Knoten über eine Kante mit dem Gewicht 19 sowie einen Alternativweg zum Knoten mit der 23. 7+11 sind jedoch kürzer, also wird der Wert und der Vorgänger aktualisiert.
  28. Die 7 ist damit abgeschlossen und weiter geht es mit der 12. 20 ist dieses Mal jedoch nicht mehr kürzer als 18, also wird mit dem nächsten unerledigten Knoten weitergemacht, eine 26er-Verbindung
  29. ins Neuland. 18 ist dann der neue kleinste Knoten und unterbietet direkt den Wert von gerade eben.
  30. Das Gegenteil ist beim Weg zur 26 der Fall. Zur Auswahl bleiben dann nur noch 2 Knoten.
  31. Einmal mit einem Holzweg, aber immerhin noch einer Neuentdeckung. Die Freude währt jedoch nur kurz, denn von der 32 geht noch ein kürzerer Weg aus.
  32. Der Algorithmus terminiert, sobald alle Knoten als erledigt markiert wurden. Zum Schluss lässt sich dann von jedem Knoten der Abstand und über die gespeicherten Vorgänger
  33. auch der kürzeste Weg zum Startknoten ermitteln. Der dargestellte Weg hat eine Länge von 40 mit Zischenstationen bei 32, 18 und 7 vom
  34. Startknoten entfernt. In der neunten Programmierübung wird der Algorithmus schließlich in einer Dijkstra-Methode
  35. umgesetzt. Sie empfängt als String den Startknoten und fragt mit diesem das Vertex-Objekt in der
  36. VertexHashmap ab. Ziel ist es, für jede Vertex-Instanz in der Variable distance die Entfernung zum Startknoten
  37. und in previousVertex den Vorgänger auf dem Weg zu speichern. Der Algorithmus beginnt dann, den Startknoten orange zu markieren.
  38. Umgesetzt wird das, indem ein Path-Objekt instanziert wird. Ein Path speichert einfach nur den Vertex und seine Distanz vom Startknoten.
  39. Außerdem wurde eine PriorityQueue mit dem Namen „paths“ instanziert. In ihr werden Path-Objekte, also orange Knoten, gespeichert und automatisch nach ihrer Distanz
  40. sortiert. Damit die Objekte miteinander verglichen werden können, implementieren Path-Objekte das Comparable-Interface.
  41. Wenn dann in der While-Schleife mit remove ein Path aus der PriorityQueue entnommen wird, handelt es sich dabei um denjenigen mit der geringsten Distanz.
  42. Die While-Schleife terminiert erst, wenn keine Pfade mehr übrig sind und alle Knoten besucht wurden.
  43. Jeder neue blau markierte Knoten wird dort als besucht markiert und die Zahl der besuchten Knoten um 1 erhöht.
  44. Sofern nicht ein abgearbeiteter Knoten in der PriorityQueue war, bei dem der Durchlauf mit „continue“ sofort mit einem neuen Knoten von vorne beginnt, werden in der For-Schleife
  45. darunter nun für den blauen Knoten alle Kanten durchgegangen. Wenn für den Zielknoten der Kante die Distanz von früheren Durchläufen noch größer als
  46. die des Anfangsknotens + dem Gewicht der Kante ist, werden die Distanz und der previousVertex aktualisiert und der entdeckte Knoten der PriorityQueue hinzugefügt.
  47. In der Übung wird die Dijkstra-Methode dann aufgerufen und es lässt sich für die Vertex-Objekte in der Variable distance ablesen, wie weit der Knoten vom Startknoten entfernt ist und
  48. welcher Vorgänger gewählt wurde. Vielen Dank für Ihre Aufmerksamkeit.

Zum Nachlesen

Dijkstra-AlgorithmusDer Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy-Algorithmen und löst das Problem der … Algorithmus von PrimDer Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen. Algorithmus von Floyd und WarshallDer Floyd-Warshall-Algorithmus basiert auf dem Prinzip der dynamischen Programmierung. ... Algorithmus von Dijkstra · Bellman-Ford-Algorithmus. Literatur. Kürzester PfadFür nichtnegative Gewichtsfunktionen lassen sich der Dijkstra-Algorithmus bzw. der A*-Algorithmus anpassen, um die kürzesten Wege zu allen Knoten des Graphs …