APSP , auch all-pairs shortest paths , sucht alle kürzesten Pfade zwischen allen Knotenpaaren.
Vorbereitung
Annahmen
Sei gerichteter Graph mit Gewichtung negativen Zyklen hat.
Speicherung der Knoten
Da wir allein für die Ausgabe der kürzesten Wege eine quadratische Laufzeit erzielen werden (jeder Knoten zu jedem anderen Knoten,
Wir können deshalb auf die Verwendung einer Adjazenzliste verzichten und gleich eine Adjazenzmatrix
Wir definieren also eine Gewichtungs-/Eingabematrix : Sei Matrix mit
Misplaced & 0 & \text{für $i=j$} \\ w(i, j) & \text{für $i \neq j$, $(i, j) \in E$} \\ \infty & \text{für $i \neq j$, $(i, j) \notin E$} \end{cases}$$ ### Ausgabe Die Werte der kürzesten Wege von einem Knoten zu einem anderen Knoten werden in der **Distanzmatrix** $D = (d_{i,j})$ zurückgegeben. Dabei enthält der Wert $d_{i, j}$ genau das Gewicht/den Wert eines kürzesten Weges von $i$ nach $j$, d.h. $d_{i,j} = \delta(i,j)$. Als Pardon zum Vorgängerfeld (wie bei [[Dijkstra-Algorithmus]] der Wert `pred`), definieren wir eine **Vorgängermatrix** $\pi = (\pi_{i, j})$ mit: - $\pi_{i,j}$ = NULL, wenn $i = j$ oder es existiert kein Weg von $i$ nach $j$ - $\pi_{i,j}$ = Vorgänger von $j$ auf einem kürzesten Weg, wenn ein Weg von $i$ nach $j$ existiert Zur Veranschaulichung kann man noch für jeden Knoten $i$ den **Vorgänger-Teilgraph** $G$ definieren, der die Vorgänger im kürzesten Pfad vom Startknoten $i$ zu einem beliebigen Knoten $j$ speichert. Er ist definiert durch: - $G_{\pi, i} = (V_{\pi, i}, E_{\pi, i})$ mit - $V_{\pi, i} = \{j \in V \ | \ \pi_{i, j} \neq \text{NULL}\} \cup \{i\}$ und - $E_{\pi, i} = \{(\pi_{i,j}, j) \ | \ j \in V_{\pi, i} \setminus \{i\}\}$ #### Pseudocode ```php // kein richtiger PHP code, nur fürs highlighting PrintAPSP(predecessorMatrix, i, j): if(i == j) print i else predecessor = predecessorMatrix[i][j] if(predecessor == null) return "Kein Weg!" else PrintAPSP(predecessorMatrix, i, predecessor) print j ``` Laufzeit: $O(|V|)$ ## Algorithmus ### Pseudocode - APSP($W$) - $n = |V|$ - $L^{(1)} = W$ *Das kleinste Gewicht eines Weges mit Länge 1 ist ja einfach die Gewichtsmatrix* - Für $m=2$ bis $n-1$ - $L^{(m)}$ = ExtendShortestPaths($L^{(m-1)}$, $W$) - Rückgabe: $L^{(m)} = L^{(n-1)}$ <div/> - ExtendShortestPaths($L$, $W$) - $n = |V|$ - Sei $L' = (l_{i,j}')$ eine $n \times n$ Matrix - Für $i=1$ bis $n$ - Für $j = 1$ bis $n$ - $l_{i,j}' = \infty$ - Für $k=1$ bis $n$ - $l_{i,j}' = \min(l_{i,j}', l_{i,k} + w_{k, j})$ - Rückgabe: $L'$ Wir iterieren durch 4 for-schleifen, deshalb landen wir bei einer **Laufzeit** von $\Theta(|V|^4)$. ### Vorgehensweise Es wird durch alle Zeilen $i$ und alle Spalten $j$ iteriert (= es wird durch alle Kanten iteriert), und dabei überprüft ob es billiger wäre, die jeweilige Kante aufzuteilen in einen bereits berechneten kürzesten Weg von $i$ nach irgend einem Knoten $k$ + dem Knoten von $k$ nach $j$. ![[apsp_gewichteter_graph.png|400]] ![[apsp_tabelle.png]] ### Laufzeitoptimierung - ExtendShortestPaths ähnelt in seiner Struktur [[Matrixmultiplikation]] und ist insbesondere [[Assoziativität|assoziaziv]]. *Der einzige Unterschied liegt darin, dass man die Werte nicht multipliziert und dann addiert, sondern die Werte addiert und dann das Minimum bildet. Die schleifen bleiben ja gleich, also man muss eigentlich genau so durch die Matrizen durchgehen wie beim Multiplizieren.* - Durch **wiederholtes Quadrieren** kann eine bessere Laufzeit erzielt werden. Beispiel: $M^8$ kann zwar durch $M^8 = M \cdot M \cdot M \cdot M \cdot M \cdot M \cdot M \cdot M$ (Laufzeit $\Theta(|V|)$), schneller jedoch durch $M^8 = (((M^1)^2)^2)^2$ (Laufzeit $\Theta(\log |V|)$) berechnet werden. - Da es keine negativen Zyklen gibt, gilt $L^{(m)} = L^{(|V|-1)}$ für alle $m \geq |V| - 1$, was für uns den Vorteil bringt, dass, falls die Potenz keine Zweierpotenz ist, wir zwar eigentlich über das Ergebnis "hinausschießen", es sich aber sowieso nicht mehr ändert. Mit folgender Optimierung im Pseudocode können wir die **Laufzeit** auf $\Theta(|V|^3 \log |V|)$ verbessern: - FasterAPSP($W$) - $n = |V|$ - $m = 1$ - $L^{(1)} = W$ - Solange $m < n-1$ - $L^{(2m)}$ = ExtendShortestPaths($L^{(m)}$, $L^{(m)}$) - $m = 2m$ - Rückgabe: $L^{(m)} = L^{(n-1)}$ Für [[Dünner Graph|dünne Graphen]] wäre der [[Bellmann-Ford-Algorithmus]] immer noch schneller, weitere Laufzeitverbesserungen bringt der [[Floyd-Warshall-Algorithmus]]. <!-- ALTE NOTIZEN ### Prinzip Bei der Umsetzung des Algorithmus nutzen wir das Paradigma der [[Dynamische Programmierung|dynamischen Programmierung]]. Wir erinnern uns an die [[Optimale Substruktur kürzester Wege]]. Daraus kann ein Weg wie folgt charakterisiert werden: - Ein Weg $p$ von $i$ nach $j$ enthält $m \leq |V|-1$ Kanten - Sind $i$ und $j$ gleich, hat der Weg das Gewicht $0$ und keine Kanten - Sind $i$ und $j$ ungleich: - So lässt sich die letzte Kante vom Weg abtrennen - Dann gibt es einen Weg von $i$ nach $k$ und eine Kante von $k$ nach $j$ - Der Weg von $i$ nach $k$ enthält maximal $m-1$ Kanten - Außerdem ist er ein kürzester Weg von $i$ nach $k$ und es gilt $\delta(i,j) = \delta(i,k) + w_{k,j}$ *Das ist der springende Punkt. Das Gewicht von k nach j kann ich ja einfach ablesen, das steht ja in der Gewichtungsmatrix. Damit delegiere ich das Problem des kürzesten Weges von i nach j auf das Problem des kürzesten Weges von i nach k.* Damit können wir weitergehen: Sei $l_{i,j}^{(m)}$ das kleinste Gewicht eines Weges von $i$ nach $j$ mit höchstens $m$ Kanten. Dann gilt für $m=0$: $$l_{i,j}^{(m)} = \begin{cases} 0 & i = j \\ \infty & i \neq j \end{cases}$$ *Das ist unser Rekursionsende.* Für $m \geq 1$ gilt: $$l_{i,j}^{(m)} = \min\left(l_{i,j}^{(m-1)}, \min_{1 \leq k \leq n} \left\{l_{i,k}^{(m-1)} + w_{k,j}\right\}\right) = \min_{1 \leq k \leq n} \left\{l_{i,k}^{(m-1)} + w_{k,j}\right\}$$ *Der Wert des kürzesten Weges von i nach j mit m Kanten ist rekursiv definiert.* *- Wir delegieren das Problem des kürzesten Weges von i nach j über m Kanten auf das Problem des kürzesten Weges über m-1 Kanten. Da muss man sich erst dran gewöhnen, aber der Weg über m-1 Kanten ist ja schon berechnet. Erinnerung: Kein divide and conquer, sondern dynamisch, wir fangen am Rekursionsende an.* *- Beim Kante abspalten könnte man jedoch eine * Da es keine negativen Zyklen gibt, gilt zusätzlich: $$\delta(i,j) = l_{i,j}^{(|V|-1)} = l_{i,j}^{(|V|)} = l_{i,j}^{(|V|+1)} = \dots$$