Cammino minimo da un nodo

P

Dato un grafo orientato G=(V,A)G=(V,A) con un costo cijc_{ij} su ogni arco e un nodo origine ss, si cercano i cammini semplici di costo minimo da ss a tutti gli altri n−1n-1 nodi (albero dei cammini minimi, SPT). Con una sola destinazione dd il problema è SP. xijx_{ij} conta quanti cammini usano l'arco (i,j)(i,j).

min⁡ ∑(i,j)∈Acijxijs.a. ∑j∈FS(i)xij−∑j∈BS(i)xji={n−1i=s−1i≠s∀ i∈Vxij≥0∀ (i,j)∈A\begin{aligned} \min\ & \sum_{(i,j)\in A}c_{ij}x_{ij}\\ \text{s.a.}\ & \sum_{j\in FS(i)}x_{ij}-\sum_{j\in BS(i)}x_{ji}=\begin{cases}n-1 & i=s\\ -1 & i\neq s\end{cases} && \forall\, i\in V\\ & x_{ij}\ge 0 && \forall\,(i,j)\in A \end{aligned}

Perché è facile

Con cicli di costo negativo il problema è in generale difficile. Senza, e in particolare con cij≥0c_{ij}\ge 0, si risolve in tempo polinomiale: la matrice dei vincoli ha un 11 e un −1-1 in ogni colonna ed è totalmente unimodulare, e Dijkstra costa O(n2)O(n^2).

Da ricordare

  • Per SP si pone bs=1b_s=1, bd=−1b_d=-1 e bi=0b_i=0 negli altri nodi.
  • Un nodo non raggiungibile si collega a ss con un arco artificiale di costo M≥(n−1)cmax⁡+1M\ge(n-1)c_{\max}+1.
  • Con un arco negativo Dijkstra può sbagliare.

Algoritmi

Fonti: dispensa §4.4, §4.5 e §4.5.1, Teorema 4.5.1, appunti Lezione 10, §1-5.