Algorithmus der Woche – Kürzeste Wege

Weitere Informationen

Wie erkläre ich das anderen Leuten am besten?
Verwenden Sie doch den bereitgestellten Foliensatz!
Ist der Algorithmus von Dijkstra auf Straßennetze beschränkt?
Dijkstras Algorithmus ist viel allgemeiner, als es den Anschein hat. Zum Beispiel benötigt er keine Kenntnis über die geografische Position eines Knotens. Man ist auch nicht auf (räumliche) Abstände beschränkt, sondern könnte z. B. Reisezeiten als Fadenlängen verwenden. Das ganze funktioniert sogar bei Einbahnstraßen oder unterschiedlichen Reisezeiten für Hin- und Rückrichtung, denn unser Algorithmus betrachtet die Länge eines Fadens immer nur in Richtung vom Start zum Ziel.
Korrektheit: Wieso findet Dijkstras Algorithmus die gleichen Entfernungen wie der („offensichtlich“ korrekte) Bindfadenalgorithmus?
Wichtigster Unterschied ist, dass der Bindfadenalgorithmus kontinuierlich vorgeht, Dijkstras Algorithmus schrittweise. Die verschiedenen Mengen der Knoten ändern sich jedoch nur dann, wenn ein Knoten von der Tischplatte abgehoben wird. Genau diese Punkte werden jedoch von Dijkstras Algorithmus abgearbeitet. Da er immer den Knoten mit dem kleinsten Abstand zu den schon schwebenden nimmt, verpasst er auch nie einen solchen entscheidenden Moment.
Streng formal kann man die Korrektheit per Induktion über die Schritte beweisen: Zu jedem Zeitpunkt ist die Menge der Knoten V aufgeteilt in schwebende S und liegende V\S, der Startknoten sei s. Induktions-Annahme: (1) Für x element S ist d[x] die Länge des kürzesten Weges von s nach x. (2) Für x element V\S ist d[x] die Länge des kürzesten Weges von s nach x, bei dem jeder Knoten außer x zu S gehört. Induktions-Schritt: Der Knoten v wird in S aufgenommen. Damit bleibt (1) erfüllt, denn falls ein kürzerer Weg existieren würde, dann würde dieser einen anderen Knoten x element V\S benützen. Dieser jedoch ist weiter weg von s als v, denn d[x]>d[v], also kann darüber kein kürzerer Weg führen. Die Zeilen 5 und 6 im Algorithmus sorgen dafür, dass (2) erhalten bleibt. Wenn der Algorithmus endet, gibt es keine (erreichbaren) Knoten mehr in S, also steht in d[] für jeden Knoten die Länge des kürzesten Wegs.
Wie finde ich den nächsten Knoten effizient?
Eine Prioritätswarteschlange ist eine Datenstruktur, zu der Elemente hinzugefügt werden können und das „kleinste“ davon schnell herausgefunden werden kann. Das kann aber ziemlich kompliziert werden, dabei entscheidet sich aber auch, wie schnell der Algorithmus läuft.
Was passiert bei negativen Abständen? (Zum Beispiel wenn ich in einer Straße sowieso noch etwas Wichtiges zu erledigen hätte und damit letztlich Zeit einspare?)
Zunächst einmal darf es keine Rundreise geben, die insgesamt eine negative Länge hat. Ansonsten könnte man beliebig lang im Kreis herumfahren, der Weg würde immer kürzer werden, es gäbe also keinen kürzesten mehr. Doch auch mit lösbaren negativen Abständen ist der Algorithmus von Dijkstra überfordert. Eine in dieser Beziehung bessere Alternative ist der Algorithmus von Bellman und Ford. Der Algorithmus von Floyd und Warshall berechnet sogar gleich alle kürzesten Wege, also zwischen allen Paaren von Knoten.
Geht es noch schneller? Müssen wir für den schnellsten nach Barcelona tatsächlich das gesamte Straßennetz Westeuropas inspizieren? Bis hinunter zum letzten Feldweg? Was machen kommerzielle Navigationssysteme?
Bei sehr großen Straßennetzen geht auch der Computer am besten vor wie der Mensch intuitiv: zunächst nur die großen Straßen und Autobahnen berücksichtigen, und nur im Start- und Zielgebiet die schmaleren. Diese Highway Hierarchies sind aktuelles Forschungsthema. Ansonsten gibt es viele weitere Verfahren, die Berechnung zu beschleunigen. Man kann z. B. von beiden Seiten gleichzeitig beginnen oder geographische Zusatzinformationen miteinbeziehen.
In welchen anderen Anwendungen werden kürzeste Wege benötigt?
Zum Beispiel beim Weiterleiten von Datenpaketen durchs Internet werden kürzeste Wege verwendet. Dabei bezieht sich „kürzest“ aber mehr auf zeitliche Verzögerung und Kosten.
Wo finde ich Beispielcode?
Es ist nicht einfach „den“ für Dijkstras Algorithmus anzugeben, da er wesentlich von der verwendeten Datenstruktur abhängt: eine Beispiel-Variante
Wer war Dijkstra?
Edsger W. Dijkstra war ein berühmter Informatiker. Er lebte von 1930 bis 2002. Dijkstra erfand nicht nur den hier vorgestellten Algorithmus, sondern lieferte auch wichtige Beiträge zu strukturierten Programmierung. Im Jahr 1972 erhielt er den Turing Award, die höchste Auszeichnung für einen Informatiker.