Cammini minimi fra tutte le coppie

P

Dato un grafo orientato G=(V,A)G=(V,A) con un costo cij∈Rc_{ij}\in\mathbb{R} su ogni arco, si cercano i cammini di costo minimo da ogni nodo a ogni altro nodo. È un albero dei cammini minimi per ogni origine ss, con le variabili xijsx^s_{ij}.

min⁡ ∑s∈V∑(i,j)∈Acijxijss.a. ∑j∈FS(i)xijs−∑j∈BS(i)xjis={n−1i=s−1i≠s∀ s,i∈Vxijs≥0∀ s∈V, (i,j)∈A\begin{aligned} \min\ & \sum_{s\in V}\sum_{(i,j)\in A}c_{ij}x^s_{ij}\\ \text{s.a.}\ & \sum_{j\in FS(i)}x^s_{ij}-\sum_{j\in BS(i)}x^s_{ji}=\begin{cases}n-1 & i=s\\ -1 & i\neq s\end{cases} && \forall\, s,i\in V\\ & x^s_{ij}\ge 0 && \forall\, s\in V,\ (i,j)\in A \end{aligned}

Perché è facile

Senza cicli negativi basta un albero dei cammini minimi per ogni origine. Con costi non negativi Dijkstra ripetuto da ogni nodo costa O(n3)O(n^3); Floyd-Warshall costa O(n3)O(n^3) anche con costi negativi.

Da ricordare

  • Ricorrenza: ch[i,j]=min⁡{ch−1[i,j], ch−1[i,h]+ch−1[h,j]}c^h[i,j]=\min\{c^{h-1}[i,j],\ c^{h-1}[i,h]+c^{h-1}[h,j]\}.
  • Il cammino da ii a jj si legge all'indietro sulla riga ii della matrice dei predecessori pp.
  • Il modello si spezza in un problema SPT indipendente per ogni origine.

Algoritmi

Fonti: dispensa §4.5.2, Esempio 4.5.2, appunti Lezione 10, §7.