Open Access

Alexander Schickedanz

• The single-source shortest-path problem is a fundamental problem in computer science. We consider a generalization of the shortest-path problem, the $k$-shortest path problem. Let $G$ be a directed edge-weighted graph with $n$ nodes and $m$ edges and $s,t$ be two fixed nodes. The goal is to compute $k$ paths $P_1,\dots,P_k$ between two fixed nodes $s$ and $t$ in non-decreasing order of their length such that all other paths between $s$ and $t$ are at least as long as the $k$\nth path $P_k$. We focus on the version of the $k$-shortest path problem where the paths are not allowed to visit nodes multiple times, sometime referred to as $k$-shortest simple path problem. The probably best known $k$-shortest path algorithm is Yen's algorithm. It has a worst-case time complexity of O(kn\cdot scp(n,m)), where scp(n,m) is the complexity of the single-source shortest-path algorithm used as a subroutine. In case of Dijkstra's algorithm scp(n,m) is O(m + n\log n). One of the more recent improvements of Yen's algorithm is by Feng. Even though Feng's algorithm is much faster in practice, it has the same worst-case complexity as Yen's algorithm. The main results presented in this thesis are upper bounds on the average-case of Yen's and Feng's algorithm, as well as practical improvements and a parallel implementation of Yen's and Feng's algorithms including these improvements. The implementation is publicly available under GPLv3 open source license. We show in our analysis that Yen's algorithm has an average-case complexity of O(k \log(n)\cdot scp(n,m)) on G(n,p) graphs with at least logarithmic average-degree and random edge weights following a distribution with certain properties. On G(n,p) graphs with constant to logarithmic average-degree and uniform random edge-weights over $[0;1]$, we show an average-case complexity of O(k\cdot\frac{\log^2 n}{np}\cdot scp(n,m)). Feng's algorithm has an even better average-case complexity of O(k\cdot scp(n,m)) on unweighted G(n,p) graphs with logarithmic average-degree and for constant values of $k$. We further provide evidence that the same holds true for G(n,p) graphs with uniform random edge-weights over $[0;1]$. On the practical side, we suggest new heuristics to prune even more single-source shortest-path computations than Feng's algorithm and evaluate all presented algorithms on G(n,p) and Grid graphs with up to 256 million nodes. We demonstrate speedups by a factor of up to 40 compared to Feng's algorithm. Finally we discuss two ways to parallelize the suggested algorithms and evaluate them on grid graphs showing speedups by a factor of 2 using 4 threads and by a factor of up to 8 using 16 threads, respectively.
• Das Kürzeste-Wege-Problem ist eines der klassischen und fundamentalen Probleme in der theoretischen Informatik. Eine Verallgemeinerung ist das sogenannte k-Kürzeste-Wege-Problem. Dabei werden in einem Graphen G mit n Knoten und m Kanten die k-kürzesten Wege zwischen zwei Knoten s und t in nicht-absteigender Reihenfolge nach der Gesamtlänge gesucht. Wir beschäftigen uns ausschließlich mit der Auf englisch “loopless” oder “simple” genannt. Variante des k-Kürzeste-Wege-Problems, in der nur kreisfreie Wege betrachtet werden, d. h. kein Knoten auf einem solchen Weg darf mehrfach besucht werden. Das k-Kürzeste-Wege-Problem taucht in vielen Anwendungen auf wie z. B. Routing in verschiedenen Netzwerken und vielfältigen anderen Optimierungsproblemen wie z. B. die Konstruktion virtueller Netzwerke, Chip-Layout Optimierung, Optimierung von Gruppentestungen und Optimierung von Datenbankanfragen. Einer der bekanntesten k-Kürzeste-Wege-Algorithmen Yens Algorithmus: RAbschnitt 3.2.1 ist Yens Algorithmus. Ausgehend vom i-ten kürzesten Weg Pi, wird für jeden Knoten auf dem Weg eine kürzeste Verzweigung berechnet und diese in einer Liste von Kandidaten gespeichert. Eine Verzweigung ist hier ebenfalls ein Weg von s nach t, der bis zum Verzweigungsknoten mit dem Weg, von dem er abzweigt, übereinstimmt. Vom Verzweigungsknoten aus wird dann eine andere Kante verwendet als im ursprünglichen Weg Pi. Für den restlichen Verlauf der Verzweigung gibt es keine weiteren Einschränkungen, d. h. die Verzweigung kann im Anschluss wieder Kanten verwenden, die bereits in Pi verwendet wurden, solange die Verzweigung kreisfrei bleibt. Der i+1 kürzeste Weg wird dann aus der Liste von Kandidaten ausgewählt, die sowohl die neuen Kandidaten des i-ten Wegs als auch die übrigen Kandidaten aus den ersten i − 1 kürzesten Wege enthält. Yens Algorithmus kommt auf eine Worst-Case-Komplexität von O(kn · spc(n,m)), wobei spc(n,m) die Laufzeit des verwendeten Kürzeste-Wege-Algorithmus ist. Die Komplexität ergibt sich daraus, dass für jeden Knoten auf jedem der kWege eine Verzweigung berechnet werden muss und schlimmstenfalls jeder Weg Θ(n) Knoten hat.