„Es ist ein großartiger Algorithmus“, sagte er Erik DemaineInformatiker am Massachusetts Institute of Technology. „Es ist sehr schnell, einfach und leicht zu implementieren.“
Um dieses Verfahren in die Praxis umzusetzen, müssen Sie sich für ein System zum Organisieren Ihrer Notizen entscheiden – eine Datenstruktur, wie es in der Fachsprache der Informatik heißt. Das hört sich vielleicht wie ein kleines technisches Detail an, aber die Zeit, die Sie damit verbringen, Ihre Notizen zu durchsuchen, wann immer Sie einen Eintrag bearbeiten oder entfernen müssen, kann einen großen Einfluss auf die Gesamtlaufzeit des Algorithmus haben.
Dijkstras Artikel verwendete eine einfache Datenstruktur, die Raum für Verbesserungen ließ. In den folgenden Jahrzehnten entwickelten Forscher bessere, liebevoll „Haufen“ genannte Haufen, in denen bestimmte Gegenstände leichter zu finden sind als andere. Sie machen sich die Tatsache zunutze, dass der Dijkstra-Algorithmus immer nur den Eintrag für den nächstgelegenen verbleibenden Scheitelpunkt entfernen muss. „Ein Heap ist im Grunde eine Datenstruktur, die es Ihnen ermöglicht, dies sehr schnell zu tun“, sagte er Vaclav RozhonForscher am Institut für Informatik, Künstliche Intelligenz und Technologie (INSAIT) in Sofia, Bulgarien.
Im Jahr 1984 entwickelten zwei Informatiker ein Cleveres Heap-Design Dies ermöglichte es Dijkstras Algorithmus, eine theoretische Grenze oder „Untergrenze“ für die Zeit zu erreichen, die zur Lösung des Problems der kürzesten Wege aus einer Quelle erforderlich war. In gewisser Hinsicht ist diese Version des Dijkstra-Algorithmus die bestmögliche. Das war fast 40 Jahre lang das letzte Wort zur Standardversion des Problems. Die Dinge änderten sich erst, als einige Forscher genauer untersuchten, was es bedeutet, „der Beste“ zu sein.
Bestes Verhalten
Forscher vergleichen Algorithmen normalerweise, indem sie untersuchen, wie sie im schlimmsten Fall abschneiden. Stellen Sie sich das verwirrendste Straßennetz der Welt vor und fügen Sie dann einige besonders verwirrende Verkehrsmuster hinzu. Wenn Sie unter diesen extremen Umständen darauf bestehen, die schnellsten Routen zu finden, ist die Version von Dijkstras Algorithmus aus dem Jahr 1984 nachweislich unschlagbar.
Aber hoffentlich hat Ihre Stadt nicht das schlechteste Straßennetz der Welt. Und so fragen Sie sich vielleicht: Gibt es einen Algorithmus, der auf jedem Straßennetz unschlagbar ist? Der erste Schritt zur Beantwortung dieser Frage besteht darin, die konservative Annahme zu treffen, dass jedes Netzwerk ungünstigste Verkehrsmuster aufweist. Dann möchten Sie, dass Ihr Algorithmus die schnellsten Pfade durch jedes mögliche Diagrammlayout findet und dabei die schlechtestmöglichen Gewichte annimmt. Forscher nennen diesen Zustand „universelle Optimalität“. Wenn Sie einen allgemein optimalen Algorithmus für das einfachere Problem hätten, einfach von einem Punkt in einem Diagramm zu einem anderen zu gelangen, könnte er Ihnen helfen, den Berufsverkehr in jeder Stadt der Welt zu umgehen.
