Home

Federica EU

1/9

Paola Festa » 21.Problemi di Cammino Minimo

Problemi di Cammino Minimo, 1

Individuare un cammino connettente due o più nodi di un grafo è un problema che compare come sottoproblema di molti altri problemi di ottimizzazione discreta ed ha, inoltre, numerosissime applicazioni nel mondo reale.

Si pensi, ad esempio, al problema di individuare un percorso tra due località riportate in una cartina stradale, in cui i vertici sono le località, mentre gli archi sono le strade che le collegano.
In tal caso, ad ogni arco è associato un costo che può essere la lunghezza in chilometri della strada o il tempo medio necessario per percorrerla (in quest’ultimo caso, dipendente dal traffico).

Se invece di un percorso qualunque, si vuole individuarne uno di costo totale minimo, allora il problema risultante è noto come problema del cammino minimo in un grafo.

Nel seguito si supporrà il caso più generale in cui il grafo istanza del problema sia orientato, per cui il costo di collegamento tra due nodi dipende dalla direzione del percorso.
Si noti che il caso di grafo orientato è più generale, dato che un grafo non orientato può sempre essere trasformato
in un grafo orientato.

Problemi di Cammino Minimo, 2

Sia

→ G=(V,A) un grafo orientato, |V|=n, |A|=m;
→ $c_{ij}\in {\mathbb R}$ il costo associato all’arco (i,j), per ogni (i,j) in A;
→ $P=\{v_1,v_2,\ldots,v_k\}$ un cammino che collega $v_1$ a $v_{k}$ visitando in sequenza i nodi intermedi $v_2,v_3,\ldots,v_{k-1}$ ed ha costo (lunghezza) totale pari a
$\displaystyle{c(P)=\sum_{i=1}^{k-1} c_{v_i\,v_{i+1}}}.$
Un cammino P che collega il nodo $v_1$ al nodo $v_k$ è detto minimo se non esiste in G un cammino alternativo di costo totale inferiore a c(P).

Tipicamente, si può essere interessati ad individuare in G

un cammino P di costo minimo da un nodo sorgente s in V ad un nodo destinazione d in V;
n-1 cammini minimi da nodo sorgente s in V ai restanti nodi di G.

Il problema 1. è noto come problema di cammino minimo singola origine – singola destinazione (SPP – Shortest Path Problem).
Il problema 2. è noto come problema dell’albero dei cammini minimi (SPT – Shortest Path Tree Problem).

Problemi di Cammino Minimo, 3

I problemi 1. e 2. ammettono soluzione se

in G non esiste un cammino P che inizia da (o passa per) il nodo origine s e che contiene un ciclo di costo negativo;
G è fortemente connesso: quest’ipotesi non è restrittiva, in quanto è sempre possibile definire pari a $+\infty$ la distanza fra nodi non connessi;
$c_{ij}\in {\mathbb Z},\ \forall (i,j)\in A$ : quest’ipotesi non è restrittiva, in quanto è sempre possibile convertire numeri razionali in numeri interi moltiplicandoli per un numero grande opportunamente scelto.

SPP, 1

Si definiscano m variabili di decisione binarie con il seguente significato:
$\forall\ \ (i,j)\in A,\ \ \ x_{ij}=\left\{ \begin{array}{lll} 1, & \mbox{{\rm se }} (i,j)\in P; \\ 0, & \mbox{{\rm altrimenti.}} \end{array} \right .$

L’obiettivo è minimizzare il costo totale del percorso P e cioè

$\min\ \displaystyle{\sum_{(i,j)\in A}c_{ij}x_{ij}}.$

Per definire i vincoli del problema, occorre imporre la semplicità del percorso soluzione P.

SPP, 2

A questo punto, si hanno tutti gli elementi per descrivere formalmente il problema SPP da un nodo s ad un nodo d diverso da s di un grafo orientato G=(V,A):

$\begin{array}{llll} \mbox{(SPP)} & \min & \displaystyle{\sum_{(i,j)\in A} c_{ij}x_{ij}}\\ & \mbox{{\rm s.a}} \\ & & \forall\ i\in V,\ \ \ \displaystyle{\sum_{j\in FS(i)}x_{ij}-\sum_{j\in BS(i)}x_{ji}}=\left\{ \begin{array}{rll} 1, & \mbox{{\rm se }} i=s; \\ -1, & \mbox{{\rm se }} i=d; \\ 0 , & \mbox{{\rm altrimenti.}} \end{array} \right .\\ \\ & & x_{ij}\in\{0,1\},\ \forall\ (i,j)\in A. \end{array}$

Nota: la matrice dei vincoli tecnologici è la matrice di incidenza nodo-arco di G ed è unimodulare. Dunque, qualunque soluzione ammissibile del rilassamento continuo avrà componenti intere.

SPT

Con analoghi ragionamenti si giunge alla descrizione matematica del problema SPT da un nodo s ai restanti nodi di un grafo orientato G=(V,A):

$\begin{array}{llll} \mbox{(SPT)} & \min & \displaystyle{\sum_{(i,j)\in A} c_{ij}x_{ij}}\\ & \mbox{{\rm s.a}} \\ & & \forall\ i\in V,\ \ \ \displaystyle{\sum_{j\in FS(i)}x_{ij}-\sum_{j\in BS(i)}x_{ji}}=\left\{ \begin{array}{ll} n-1, & \mbox{{\rm se }} i=s; \\ -1, & \mbox{{\rm altrimenti.}} \end{array} \right .\\ \\ & & x_{ij}\in\{0,1\},\ \forall\ (i,j)\in A. \end{array}$

Nota: la matrice dei vincoli tecnologici è la matrice di incidenza nodo-arco di G ed è unimodulare. Dunque, qualunque soluzione ammissibile del rilassamento continuo avrà componenti intere.

Algoritmo di Dijkstra, 1

L’algoritmo di Dijkstra risolve il problema SPP ed il problema SPT in un grafo G=(V,A), tale che $c_{ij}\geq 0,\ \forall (i,j)\in A$ (G non può contenere cicli di costo negativo).

In quanto segue faremo riferimento al problema SPT.
Gli n-1 cammini minimi da s sono memorizzati in un’arborescenza realizzata attraverso l’uso dell’array dei predecessori p[n], definito come segue:

$\forall\ i=1,2,\ldots,n,\ \ p_j=\left\{ \begin{array}{lll} 0, & \mbox{{\rm se $j$ non \`e visitato da $P$};} \\ s, & \mbox{{\rm se $j=s$};} \\ i, & \mbox{{\rm se $i$ \`e visitato da $P$ immediatamente prima di $j$.}} \end{array} \right .$

Algoritmo di Dijkstra, 2

Teorema. Sia G=(V,A) un grafo orientato. Sia S un sottoinsieme proprio di V, s in S e per ogni i in S, sia L[i] il costo del cammino minimo da s ad i (L[s]=0).
Sia, inoltre,
$(v,h)=\mbox{argmin}\ \{L[i]+c_{ij}\ \vert\ (i,j)\in \delta_G^+(S)\}.$
Se $c_{ij}\geq 0, \forall (i,j)\in A$ , allora $L[v]+c_{vh}=L[h]$ .

Dimostrazione. Per dimostrare che $L[v]+c_{vh}$ è il costo di un cammino minimo da s ad h, occorre
verificare che ogni altro percorso alternativo P non ha costo minore.

Algoritmo di Dijkstra, 2

Sia $(i,j)\in \delta_G^+(S),\ (i,j)\not=(v,h)$ , e si partizioni il percorso P in $P_1\cup\{(i,j)\}\cup P_2$ , come mostrato in Figura.

E’ evidente che
$\begin{array}{lcll} c(P) &\stackrel{\mbox{def.}}{=}& \displaystyle{\sum_{(u,w)\in P}c_{uw}}\ =\ c(P_1)+c_{ij}+c(P_2) \\ \\ &\stackrel{c(P_1)\geq L[i]}{\geq} & L[i]+c_{ij}+c(P_2)\stackrel{c(P_2)\geq 0}{\geq} L[i]+c_{ij} \\ \\ & \geq & L[v]+c_{vh}. \end{array}$