Berechnung kürzester Wege mit negativen Kantenkosten

Abstract

Das Kürzeste-Wege-Problem ist ein elementares Problem der Graphentheorie. Während sich für Graphen mit positiven Kantenkosten schon lange nahe-lineare Algorithmen wie der Dijkstra-Algorithmus etabliert haben, sind im Allgemeinen für Graphen mit beliebigen, also auch negativen Kantenkosten, nur Algorithmen mit schlechterer Komplexität bekannt. Bekannte Beispiele hierfür sind der Bellman-Ford Algorithmus oder der Goldberg-Algorithmus, die in O(nm) bzw. O(m√n log W ) laufen. Der 2022 vorgestellte Algorithmus von Bernstein et al. verspricht mit O(m log⁸(n) log W) erstmals eine nahe-lineare Komplexität, die die bestehenden Algorithmen in der Theorie verbessert. In dieser Arbeit wird Bernsteins Algorithmus vereinfacht und von Grund auf erklärt und eine praktische Implementierung vorgestellt. Außerdem wird durch Laufzeittests untersucht, wie Bernsteins Algorithmus im Vergleich mit ausgewählten bestehenden Algorithmen abschneidet. Die Tests erfolgen auf drei verschiedenen Graphklassen. Es konnte festgestellt werden, dass Bernsteins Algorithmus auf zufällig generierten Graphen mit etwa 106 Knoten um ein Vielfaches langsamer ist als eine effiziente Implementierung von Bellman-Ford (SPFA). Trotzdem konnte gezeigt werden, dass die nahe-lineare Komplexität erreicht wird. Somit ergibt sich bei der Anwendung auf praktische Probleme für Bernsteins Algorithmus kein Laufzeitvorteil, weshalb er die anderen Algorithmen erst bei weitaus größeren Eingabegraphen zeitlich überbieten kann.