Floyd-Warshall

L'algoritmo trova le distanze minime, restituendole su $D^{(n)}$, tra tutte le coppie di nodi in $V=\{1,...,n\}$, su un grafo $G$ orientato con possibili pesi negativi riportati nella matrice di adiacenza $W$:

floyd_warshall(W)
  n = W.rows = W.colums
  D = {}
  D[0] = W
  for k = 1 to n
    for i = 1 to n
      for j = 1 to n
        D[k][i,j] = min(D[k-1][i,k] + D[k-1][k,j], D[k-1][i,j])
  return D[n]

All'interno della matrice $W$, i pesi assumono valori: $$w_{ij}=\{\begin{array}{ll}0& \text{se }i=j\\ \infty & \text{se }(i,j)\notin E\\ w(i,j)& \text{altrimenti}\end{array}$$

La complessità è data dai tre cicli annidati, quindi $T(n)=\Theta (n^3)$.

Correttezza

L'algoritmo è corretto perchè alla fine, degli elementi della matrice $D^{(n)}$, si ha che $d_{ij}^{(n)}=\delta (i,j)$.

Si può dimostrare definendo ${\mathcal{D}}_{ij}$, cioè l'insieme dei cammini semplici tra $i$ e $j$, e ${\mathcal{D}}_{ij}^{(k)}$, cioè l'insieme dei cammini $p\in {\mathcal{D}}_{ij}$ i cui nodi intermedi, ovvero esclusi $i$ e $j$, hanno valore $n_i\le k$.

Con questo si può notare che ${\mathcal{D}}_{ij}^{(k-1)}\subseteq {\mathcal{D}}_{ij}^{(k)}$ e che alla fine ${\mathcal{D}}_{ij}^{(n)}={\mathcal{D}}_{ij}$ perchè tutti i nodi sono inclusi.

Si può quindi definire $d_{ij}^{(k)}$ come il costo minimo dei cammini tra $i$ e $j$ che includono fino al $k$-esimo nodo: $$d_{ij}^{(k)}=\underset{p\in {\mathcal{D}}_{ij}^{(k)}}{\min }w(p)$$ per cui alla fine $d_{ij}^{(n)}=\delta (i,j)$ perchè ${\mathcal{D}}_{ij}^{(n)}={\mathcal{D}}_{ij}$ e per la definizione $\delta (i,j)=\underset{p\in {\mathcal{D}}_{ij}}{\min }w(p)$.

Generazione matrici

La correttezza del corpo dei cicli si può dimostrare partizionando ${\mathcal{D}}_{ij}^{(k)}$ in ${\hat{\mathcal{D}}}_{ij}^{(k)}$, ovvero l'insieme dei cammini $p\in {\mathcal{D}}_{ij}^{(k)}$ passanti per $k$, e in ${\mathcal{D}}_{ij}^{(k-1)}$, ovvero l'insieme dei cammini non passanti per $k$: $${\mathcal{D}}_{ij}^{(k)}={\hat{\mathcal{D}}}_{ij}^{(k)}\cup {\mathcal{D}}_{ij}^{(k-1)}\wedge {\hat{\mathcal{D}}}_{ij}^{(k)}\cap {\mathcal{D}}_{ij}^{(k-1)}=\varnothing$$

Dalla definizione di $d_{ij}^{(k)}$ ottenuta precedentemente è quindi possibile ricavare l'espressione dell'algoritmo: $$\begin{array}{rl}{d}_{ij}^{(k)}& =\underset{p\in {\mathcal{D}}_{ij}^{(k)}}{\min }w(p)=\\ & =\min \left(\underset{p\in {\hat{\mathcal{D}}}_{ij}^{(k)}}{\min }w(p),\underset{p\in {\mathcal{D}}_{ij}^{(k-1)}}{\min }w(p)\right)=\\ & =\min \left(\underset{p\in {\mathcal{D}}_{ik}^{(k-1)}}{\min }w(p)+\underset{p\in {\mathcal{D}}_{kj}^{(k-1)}}{\min }w(p),\underset{p\in {\mathcal{D}}_{ij}^{(k-1)}}{\min }w(p)\right)=\\ & =\min \left(d_{ik}^{(k-1)}+d_{kj}^{(k-1)},d_{ij}^{(k-1)}\right)\end{array}$$ dato che, essendo semplici, i cammini passanti per $k$ si possono suddividere in due non passanti per $k$.

Ottimizzazione

L'algoritmo si può ottimizzare riducendo il numero di matrici, tenendone una per l'iterazione corrente e una per la precedente. Inoltre è anche possibile salvarne una sola, purchè si soddisfino le condizioni per cui:

1. $d_{ii}^{(k)}=0,\forall i,k=1,...,n$

   Si può dimostrare per induzione su $k$:

   • Caso base, per $k=0$: è verificato per la definizione di $W$, perchè $d_{ii}^{(0)}=w_{ii}=0$
   • Passo induttivo, assumendo che valga fino a $k-1$: $$d_{ii}^{(k)}=\min (\underset{\ge 0}{\underbrace{d_{ik}^{(k-1)}+d_{ki}^{(k-1)}}},\underset{=0}{\underbrace{d_{ii}^{(k-1)}}})=0$$ Inoltre, questo evidenzia che se $d_{ii}^{(k)}<0$, allora sarebbero presenti cicli negativi.

2. $\{\begin{array}{l}{d}_{ik}^{(k)}=d_{ik}^{(k-1)}\\ d_{kj}^{(k)}=d_{kj}^{(k-1)}\end{array},\forall i,j,k=1,...,n$

   Si può dimostrare partendo dalla definizione di $d_{ij}^{(k)}$, infatti: $$d_{ik}^{(k)}=\min \left(d_{ik}^{(k-1)},d_{ik}^{(k-1)}+d_{kk}^{(k-1)}\right)=d_{ik}^{(k-1)}$$