Kürzeste Wege mit euklidischen Distanzen: Ein erklärendes Modell

Zusammenfassung In diesem Paper wird das Problem untersucht, den kürzesten Weg zwischen einem Ursprungs- und einem Zielpunkt in Netzwerken zu finden, deren Bogenlängen euklidische Distanzen sind. Dijkstras Algorithmus und eine modifizierte Version von Dijkstras Algorithmus, die an die Netzwerktopologie besser angepasst ist, werden verglichen. Wir demonstrieren am unendlichen Gitternetzwerk mit diagonalen Bögen (einem Prototyp für allgemeinere spärliche euklidische Netzwerke), dass der adaptive Algorithmus im Durchschnitt weniger als 8,3 % der Fläche erweitert, die der Dijkstra-Algorithmus erweitern würde, und im schlechtesten Fall weniger als 10,7 %. Darüber hinaus präsentieren wir rechnerische Ergebnisse für allgemeinere Netzwerke.