Der Dijkstra-Algorithmus
Institut für Bauinformatik - TU Dresden
https://www.youtube.com/watch?v=8zE1tJLnRLI

Transkript (automatisch erstellt)

0:00 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.
0:11 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
0:21 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
0:28 den kürzesten Weg zu diesem. Im einfachsten Fall kennt der Startknoten nur eine Kante und diese führt direkt zum
0:35 Ziel. Etwas schwieriger wird die Suche bei mehreren Stationen.
0:40 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.
0:49 Von dort wird dann weiter gesucht und schließlich der letzte Knoten gefunden. Dieser ist dann 8 + die zwischengespeicherten 13 vom Startknoten entfernt.
0:58 Es wird außerdem vermerkt, welcher Knoten auf dem Weg zum Startknoten genommen wurde, sodass der Weg zurückverfolgt werden kann.
1:04 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.
1:12 Begonnen wird wieder links mit dem Startknoten und von diesem geht eine Kante mit dem Gewicht 13 aus.
1:19 Es wird also als Distanz für den Knoten die 13 gespeichert und als Vorgänger der Startknoten angegeben.
1:24 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“.
1:34 Der Startknoten kann dann als erledigt markiert werden, da alle Verbindungen, die von ihm ausgehen, überprüft wurden.
1:40 Aus den orangenen Knoten wird dann mit dem Knoten fortgefahren, der die geringste Distanz aufweist, also dem Knoten mit der 13.
1:49 Er kennt insgesamt 3 Kanten. Einmal den Weg zurück zum Startknoten, welcher jedoch als erledigt markiert wurde und deshalb
1:56 nicht weiter beachtet werden muss. Dann folgt eine Verbindung zum Zielknoten mit dem Gewicht 11, sodass sich als Gesamtdistanz
2:03 für ihn 24 ergibt. Schließlich noch eine günstige Verbindung nach unten, welche 6 Einheiten kostet.
2:09 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.
2:20 Damit sind alle Verbindungen des oberen Knoten durchsucht worden und er kann als abgeschlossen markiert werden.
2:25 Aus den orangenen Knoten wird als nächstes wieder der kleinste ausgewählt, das ist dieses Mal die 19.
2:30 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.
2:39 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.
2:49 Zum Schluss sind dann alle Knoten als erledigt markiert und kennen ihre optimale Distanz zum Startknoten.
2:56 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.
3:03 Wir beginnen mit dem Startknoten oben links und es werden drei Kanten identifiziert, welche orange markiert werden.
3:10 Der Startknoten ist damit abgearbeitet und es geht weiter mit dem kleinsten Wert, der 7.
3:16 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.
3:30 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
3:43 ins Neuland. 18 ist dann der neue kleinste Knoten und unterbietet direkt den Wert von gerade eben.
3:50 Das Gegenteil ist beim Weg zur 26 der Fall. Zur Auswahl bleiben dann nur noch 2 Knoten.
3:55 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.
4:11 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
4:20 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
4:30 Startknoten entfernt. In der neunten Programmierübung wird der Algorithmus schließlich in einer Dijkstra-Methode
4:37 umgesetzt. Sie empfängt als String den Startknoten und fragt mit diesem das Vertex-Objekt in der
4:41 VertexHashmap ab. Ziel ist es, für jede Vertex-Instanz in der Variable distance die Entfernung zum Startknoten
4:49 und in previousVertex den Vorgänger auf dem Weg zu speichern. Der Algorithmus beginnt dann, den Startknoten orange zu markieren.
4:58 Umgesetzt wird das, indem ein Path-Objekt instanziert wird. Ein Path speichert einfach nur den Vertex und seine Distanz vom Startknoten.
5:06 Außerdem wurde eine PriorityQueue mit dem Namen „paths“ instanziert. In ihr werden Path-Objekte, also orange Knoten, gespeichert und automatisch nach ihrer Distanz
5:15 sortiert. Damit die Objekte miteinander verglichen werden können, implementieren Path-Objekte das Comparable-Interface.
5:23 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.
5:32 Die While-Schleife terminiert erst, wenn keine Pfade mehr übrig sind und alle Knoten besucht wurden.
5:37 Jeder neue blau markierte Knoten wird dort als besucht markiert und die Zahl der besuchten Knoten um 1 erhöht.
5:43 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
5:52 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
6:01 die des Anfangsknotens + dem Gewicht der Kante ist, werden die Distanz und der previousVertex aktualisiert und der entdeckte Knoten der PriorityQueue hinzugefügt.
6:10 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
6:21 welcher Vorgänger gewählt wurde. Vielen Dank für Ihre Aufmerksamkeit.