floyd-warshall.md

Floyd-Warshall

Floyd-Warshall brukes til å finne den korteste veien mellom alle noder i en vektet rettet graf ved bruk av dynamisk programmering og vektmatriser og kjører i $\Theta(V^3)$ tid.

Vi antar at det IKKE er negative sykler derimot er negative kanter ok.

Den formelle definisjonen av det generelle problemet

All pairs shortest path.

Input: En vektet, rettet graf $G=(V,E)$ uten negative sykler, der $V=[1,...,n]$, og vektene er gitt av matrisen $W=(w_{ij})$
Output: En $n*n$ matrise $D=(d_{ij})$ med avstander, dvs. $d_{ij}=s(i,j)$

Returnerer en forgjengermatrise $\Pi=(\pi_{ij})$

$\pi^{(k)}_{ij}$ er forelderen til noden $j$ på den korteste veien (stien) fra noden $i$.

Tilleggskrav for korrekthet

Trinn for trinn

1. Takes in matrix $W$ ($n \times n$)
2. For each row $k$ in matrix $W$: Get the matrix $D^{k}$
3. For each vertex $i$: for each vertex $j$: find shortest path from $i$ to $j$
4. Set point in matrix equal to that path
5. Return altered matrix

Korrekthetsbevis

Styrker og svakheter sammenlignet med andre

In-place: Ja, alt skjer inne i matrisen.

	Floyd Warshall
Complexity	$O(v^3)$
Recommended graph size	Small
Good for APSP*	Yes
Can detect negative cycles	Yes
SP on graph with weighted edges	Bad in general
SP on graph with unweighted edges	Bad in general

*APSP = All Pairs Shortest Path

Kjøretid og utregning

Pensumvarianten i CLRS av FW kxsrever $\Theta(n^3)$ minne men kan reduseres til $\Theta(n^2)$ ved å droppe å lage $D^k$ matriser, slik som vi gjør i linje 4 i pseudokoden over. I stedenfor så initieres det to matriser:

$\rightarrow D$ for avstandene

$\rightarrow \Pi$ for forgjengerene

Denne endringen resulterer i en forbedret minneallokasjon og vi går fra $\Theta(n^3) \rightarrow \Theta(n^2)$.

$\Theta(V^3)$ da det er tre nøstede løkker i algoritmen.

Best case	Average case	Worst case	Minne
$\Theta(V^3)$	$\Theta(V^3)$	$\Theta(V^3)$	$\Theta(V^2)$

Python kodeeksempel