Eine der Anwendungen von topologischen Netzen ist die Berechnung des kürzesten Weges von A nach B. Dafür gibt es verschiedene Ansätze, der Dijkstra-Algorithmus ist einer davon. Er berechnet von einem gegebenen Startpunkt aus die kürzesten Wege zu allen anderen Knoten im Netz und liefert als Resultat nicht nur die Weglängen zu den anderen Knoten, sondern auch die entsprechenden Wege dorthin als Abfolge von Knoten. Die Logik des Algorithmus ist elegant und recht effizient. Man beachte allerdings, dass man nicht alle Wege (von jedem Knoten zu jedem anderen) erhält!
Und so funktioniert die Berechnung: Die Menge der Knoten wird in zwei Mengen unterteilt: Die Menge A der Knoten, die schon fertig berechnet sind und die Menge B der Knoten, deren kürzeste Wege noch nicht bekannt sind. Die erste Menge enthält natürlich zunächst nur den Startknoten (denn der kürzeste Weg zu sich selbst ist nun mal null) und die zweite Menge alle Knoten bis auf den Startknoten (weil man zu Beginn des Prozesses schließlich noch keine Information über die Wege zu den anderen Knoten hat). Des Weiteren wird eine Liste von Weglängen angelegt, in der später für jeden Knoten die Summe der Wege vom Startknoten aus steht. In diese Liste trägt man für den Startknoten den Gesamtweg 0 ein und für alle anderen Knoten den Weg "unendlich" (Man geht zunächst davon aus, dass man nicht zu diesen Knoten gelangen kann). Außerdem wird noch eine Liste angelegt, in der man für jeden Knoten den Vorgänger bezüglich seines kürzesten Weges ablesen kann. Dann werden zu der Menge A alle Nachbarknoten aus B gesucht, also alle Knoten aus B, zu denen man von irgendeinem Knoten von A aus über genau eine Kante gelangen kann. Zu jedem Nachbarknoten berechnet man den Weg und kann nun leicht feststellen, welcher Nachbarknoten die kleinste Entfernung vom Startknoten hat. Nun ist leicht einsehbar, dass es zu genau diesem Knoten keinen kürzeren Weg mehr geben kann, denn alle anderen Nachbarn weisen bereits eine größere Weglänge auf. Damit sind alle möglichen Umwege auf jeden Fall länger, egal wie sie nun liegen mögen. Also kann man diesen minimalen Nachbarn aus der Menge B herausnehmen und der Menge A hinzufügen. Gleichzeitig trägt man in die Liste der Weglängen diejenige dieses Knotens ein (Sie kann schließlich nicht mehr kleiner werden) und merkt sich in der Liste der Vorgänger den letzten Knoten, über den der kürzeste Weg zu dem aktuellen Knoten lief. Diese Aktionen führt man als Schleife so lange durch, bis die Menge A alle Knoten enthält oder bis in einem Schleifenschritt kein Nachbarknoten mehr gefunden werden kann (dann ist der Rest des Netzes vom Startknoten aus nicht erreichbar). Am Ende kann man aus der Liste der Weglängen für jeden Knoten die kürzeste Wegsumme zum Startknoten lesen. Will man nun auch den Weg vom Startknoten zum Zielknoten wissen, so ermittelt man aus der Liste der Vorgänger den Vorgänger des Zielknotens und von diesem Vorgänger wieder den Vorgänger und so weiter, bis man am Startknoten angelangt ist. (Man rollt den Weg von hinten auf.) Wie man sieht, handelt es sich um ein sehr einfaches wie elegantes Prinzip und die Berechnungskomplexität hält sich in angenehmen Grenzen (Es werden maximal so viele Schritte benötigt wie es Knoten gibt).
Bemerkung zur Lauffähigkeit: Das Applet ist getestet auf Opera, Netscape 6 und 7 und Internet Explorer 5 und höher. Voraussetzung ist ein JavaPlugin der Version 1.4.1, das man von Sun kostenfrei beziehen kann (und das natürlich im Explorer aktiviert sein muss).