31
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 1 2.3 Cammini ottimi
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 1
2.3 Cammini ottimi
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 2
2.3.1 Cammini minimi e algoritmo di Dijkstra
cij rappresenta il costo (lunghezza, tempo di percorrenza,…) dell’arco (i, j) ∈ A
t è la destinazione
1
3
2
5
4
6
3
2
6 8
1
10
4
3
9 2
4
31
s t
s è l’origine
Dato un grafo orientato G = (N, A) con una funzione di costo c : A → cij∈ e due nodi s e t , determinare un cammino di costo minimo da s a t.
R
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 3
ijN.B.: Se grafo G non orientato
i lati sono considerati come coppie di archi ji
I problemi di cammini ottimi (minimi o massimi) hannoinnumerevoli applicazioni:
• pianificazione e gestione di reti di trasporto, elettriche, idrauliche, di comunicazione,..
• pianificazione di progetti complessi (relazioni logiche tra entità)
• ...
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 4
Esempios 1 2 3
31
t
Un approccio di tipo “greedy” rispetto agli archi del taglio corrente ( simile a quello di Prim per gli alberi di supporto di costo minimo ) non è esatto !
Sδ+( S )
s 1 2 3
31
t
S
δ+( S )
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 5
= 6
= 5
s 1 2 3
31
tS
s 1 2 3
31
t
il cammino ottenuto con il procedimento “greedy” non è di costo minimo.
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 6
Algoritmo di Dijkstra
ipotesi cij ≥ 0, ∀(i, j) ∈ A con cij = +∞ se (i, j) ∉ A
1
3
2
5
4
6
3
2
6 8
1
10
4
3
9 2
4
31
s t
input G = (N, A) con n = |N| e m = |A|, un nodo s ∈ N,cij ≥ 0 ∀(i, j) ∈ A
output Cammini minimi da s a tutti gli altri nodi
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 7
Ad ogni nodo j ∈ N si associa una etichetta L[j] che al termine dell’algoritmo rappresenta il costo di un cammino minimo da s a j.
2# 1
3# 2 8# 4
6# 3
11
# 51
3
2
5
4
6
3
2
6 8
1
10
4
3
9 2
4
31
s t
Idea: Esplorare i nodi in ordine crescente del costo di un cammino minimo da s a ciascuno di essi.
# 0
0“Greedy”sui camminida s a j !
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 8
Esempio1
3
2
5
4
6
3
2
6 8
1
10
4
3
9 2
4
31
s t
Etichette associate ad ogni nodo j: [ L[j], pred[j] ]
dove pred[j] è il “predecessore” di j nel cammino minimo da s a j
1
3
23
2
S
[ 0, 1 ][ 2, 1 ]
s
3
23
2S
δ+( S )
*
0 +2 < 0 + 3
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 9
1
3
2
5
3
8
4
S
[ 3, 1 ]
[ 0, 1 ]
[ 2, 1 ]
1
3
2
5
410
4
S
[ 0, 1 ]
[ 2, 1 ]
[ 3, 1 ]
[ 6, 3 ]
S
1
3
2
5
410
2[ 0, 1 ]
[ 2, 1 ]
[ 3, 1 ]
[ 6, 3 ]
[ 8, 5 ]
δ+( S )
*
δ+( S )*
*δ+( S )
0 +3 < 2 + 4
2 +4 < 3 + 10
6 +2 < 3 + 10
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 10
S
[ 11, 4 ]
1
3
2
5
4
63[ 0, 1 ]
[ 2, 1 ]
[ 3, 1 ]
[ 6, 3 ]
[ 8, 5 ]
δ+( S )*
1
3
2
5
410
2*
S
[ 0, 1 ]
[ 2, 1 ]
[ 3, 1 ]
[ 6, 3 ]
δ+( S )
[ 8, 5 ]
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 11
Cammino minimo da s a j: pred[j], pred[ pred [j] ], ..., s
1
3
2
5
4
6
3
2
6 8
1
10
4
3
9 2
4
31
s t
[ 11, 4 ][ 0, 1 ]
[ 2, 1 ]
[ 3, 1 ]
[ 6, 3 ]
[ 8, 5 ]
Cammino di costo minimo da s a t
j= t
Cammino di costo minimo da s al nodo 2
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 12
Struttura dati
• L[ j] =⎧⎨⎩
costo di un cammino minimo da s a j, ∀ j ∈ S
min { L[i] + cij : (i, j) ∈ δ+(S) }, ∀ j ∉ S
• S ⊆ N sottoinsieme di nodi di cui le etichette sonodefinitive
...
Algoritmo di Dijkstra
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 13
S
e il sottoinsieme corrente dinodi S ⊂ N,
L[v] + cvh = min { L[i] + cij : (i, j) ∈ δ+(S) }
cioè L[v] + cvh ≤ L[i] + cij ∀(i,j) ∈ δ+(S)
Dato grafo G orientato
s
e si individua (v,h) ∈ δ+(S) tale che:
L[h]
L[j]j
L[i]=5
icij = 1
L[v]=3v
hcvh = 2
si considera il taglio orientato δ+(S)
δ+( S )
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 14
“predecessore” di j nel cammino minimo da s a j∀ j ∈ S
• pred[j] =
ij vj
ij
ct.c . L[ ]+ m in L[i] + i
+ j
= { c : S}
con = se (i,j) A S
c
v v
∀
∈
∞ ∉ ∉
⎧⎪⎪⎪⎨⎪⎪⎪⎩
S
s
δ+(S)
L[ j]=5
pred[ j]=vL[v]=3v
jcvj = 2
L[i]=5i
cij = 1
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 15
BEGIN
S := {s}; L[s] := 0;
pred[s] := s;
WHILE |S| ≠ n DO
individuare (v,h) ∈ δ+(S) ={ (i,j) : (i,j)∈A, i∈S, j∉S} t.c.
L[v] + cvh = min { L[i] + cij : (i,j) ∈ δ+(S) };
L[h] := L[v] + cvh;
pred[h] := v;
S := S ∪ {h};
END-WHILE
END
NB: Se δ+(S)=∅, l’algoritmo finisce: nessun h ∈ N \ S è raggiungibile da s
taglio uscente
input G = (N, A), n = |N|, m = |A|, s ∈ N, cij ≥ 0 ∀ (i, j) ∈ A
output Cammini minimi da s a tutti gli altri nodi
Algoritmo di Dijkstra
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 16
Complessità
Se scansione esplicita di tutti m archi scartando quelli che non appartengono a δ+(S), complessità totalesarebbe O(nm), ossia O(n3) per i grafi densi.
Determinando le etichette (qui L[j]) per aggiornamento (≈ algoritmo di Prim) basta considerare un solo arco di δ+(S) per ogni nodo j∉S ⇒ complessità totale O(n2).
Dipende da come, ad ogni iterazione, viene individuatol’arco (v,h) del taglio uscente δ+(S).
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 17
L’algoritmo di Dijkstra è esatto.
Dim.
• base induttiva : è vero per p = 1 : S = {s}, L[s] = 0 e L[ j] = csj ∀ j ≠ s
Proprietà
• passo induttivo : se è vero al p-esimo passo, lo è anche al (p+1)-esimo
Al p-esimo passo: S = {s, i2, ..., ip} e
L[ j ] =⎧⎨⎩
costo di un cammino minimo da s a j, ∀ j ∈ S
costo di un cammino minimo con tutti i nodi intermedi in S ∀ j ∉ S
Per induzione sul numero p di passi :
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 18
(p+1)-esimo passo: Sia h ∉ S il nodo che viene inserito in S e ϕ il cammino da s a h tale che:
L[v] + cvh ≤ L[i] + cij ∀ (i, j) ∈ δ+(S)
c(π) = c(π1) + cij + c(π2) ≥ L[i] + cij ≥ L[v] + cvh
i
S
π
c(π1) ≥ L[ i ]: per ipotesi induttiva c(π2) ≥ 0 perché cij ≥0
s
hv
j per scelta di (v,h) costo c(ϕ)
esistono i∈S e j∉S tali che π = π1 ∪ (i, j) ∪ π2 dove
(i, j) è il primo arco ∈ π ∩ δ+(S)ϕ
π2
π1
L[v]
Verifichiamo che per qualsiasi cammino π da s a h si ha c(π) ≥ c(ϕ)
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 19
s
3
2
5
4
t
3
2 42
3
I cammini minimi da s a tutti i nodi j sono memorizzati mediante il vettore dei predecessori
I cammini minimi da s a tutti gli altri nodi formanoun albero (albero dei cammini minimi).
[ 11, 4 ][ 0, 1 ]
[ 2, 1 ]
[ 3, 1 ]
[ 6, 3 ]
[ 8, 5 ]
j=t
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 20
Il costo da 1 a 3 non è più modificato dopo il primo passo. Tramite una scelta “greedy” sui cammini uscenti dal nodo 1 viene preso pari a c13 che è “localmente” migliore (c13 < c12) anche se il cammino 1→2→3 ha un costo totale inferiore causa la presenza di c23 < 0.
L’algoritmo di Dijkstra non è applicabile se esistono archi di costo cij < 0
Esempio
1
2
3
4
2 1
-2
1 1
In questo caso, otteniamo il cammino 1→3→4 di costo 2mentre esiste il cammino 1→2→3→4 di costo 1
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 21
Esercizio Determinare i cammini minimi dal nodo 0 a tutti gli altri nodi del seguente grafo:
5
76
4
0 1
3
2
4 0
1 42
2
1
13
3 32
2
1
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 22
2.3.2 Algoritmo di Floyd-Warshall
N.B.: Se il grafo contiene circuiti di costo totale negativo, il problema non è ben definito!
st
1
3
2-6
2Esempio
costo: -1
Permette di determinare i cammini minimi tra tutte le coppie di nodi s, t anche in presenza di archi di costo negativo.
L’algoritmo di Floyd-Warshall permette di individuarel’esistenza di circuiti di costo negativo
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 23
input
output
Struttura dati: due matrici n x n D e P di cui gli elementi rappresentano al termine dell’algoritmo
Grafo orientato G = (N, A) descritto mediante la matrice n x n dei costi cij.
Per ogni coppia di nodi i, j ∈ N, il costo dij di un cammino minimo da i a j.
Algoritmo di Floyd-Warshall
• dij = costo di un cammino minimo da i a j• pij = predecessore di j nel cammino minimo da i a j
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 24
1
3
2 43
2
6 8
1
-10
9
Esempio
D
091∞4
∞08∞3
-1060∞2
∞2301
4321
44444
33333
22222
11111
4321
P
Algoritmo di Floyd-Warshall
Per (i, j) ∈ A si pone dij= cij, per gli auto-anelli dii= 0 e per (i, j) ∉ A si pone dij = ∞
La matrice dei predecessori viene inizializzata con pij = i
n.b.: da a e da a .
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 25
Ciclo h=1 :
Per ogni coppia di nodi i, j (compreso casi i=j) si controlla se per andare da i a j conviene passare per h (=1): di1 + d1j < dij = cij
Poiché non esistono tali archi, le matrici D e P rimangono invariate
Operazione triangolare relativa al nodo h:
i
jh
dij
dih
dhj
1
3
2 43
2
6 8
1
-10
9
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 26
D P
091∞4
∞08∞3
-1060∞2
-72301
4321
44444
33333
22222
21111
4321
- Per andare da 1 a 4 conviene passare per 2: d14 = ∞ mentre il cammino (1,2) ∪ (2,4) è di costo d12 + d24 = 3 – 10 = -7
Il costo d14 viene rimpiazzato col costo del nuovo cammino d12 +d24
Poiché il predecessore di 4 nel nuovo cammino è 2 si pone p14 =2
Ciclo h=2 :
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 27
D P
091∞4
-208∞3
-1060∞2
-72301
4321
44444
23333
22222
21111
4321
- Per andare da 3 a 4 conviene passare per 2: d34 = ∞ mentre il cammino (3,2) ∪ (2,4) è di costo d32 + d24 = 8 – 10 = -2
Poiché il predecessore di 4 nel nuovo cammino è 2 si pone p34 =2
Il costo d34 viene rimpiazzato col costo del nuovo cammino d32 +d24
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 28
- Per andare da 4 a 3 conviene passare per 2: d43 = 9 mentre il cammino (4,2) ∪ (2,3) è di costo d42 + d23 = 1 + 6 = 7
Riguardo gli auto-anelli, si nota che passando per 2 il cammino da 4 a se stesso risulta di costo 1 - 10 = - 9 < d44 = 0
Alla fine del ciclo h = 2 le matrici dei costi e dei predecessori sono:
D
-971∞4
-208∞3
-1060∞2
-72301
4321P
22444
23333
22222
21111
4321
Esiste quindi un circuito (4→2→4) di costo negativo !
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 29
BEGINg
FOR i:=1 TO n DO
FOR j:=1 TO n DO pij := i; END-FOR
END-FOR
FOR h:=1 TO n DO /* operazione triangolare su h */
FOR i:=1 TO n WITH i ≠ h DO
FOR j:=1 TO n WITH j ≠ h DOIF (dih + dhj < dij) THEN
dij = dih + dhj ;
pij:= phj ;
END-IF
END-FOR
END-FOR
FOR i:=1 TO n DO
IF dii < 0 THEN STOP; END-IF /* ∃ un circuito negativo */
END-FOR
END-FOR
END
Operazione triangolare: Si aggiorna dij se dal punto di
vista del costo risulta piùconveniente raggiungere j da
i passando per h
Algoritmo di Floyd-Warshall
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 30
Complessità
Nel caso peggiore l’operazione triangolare viene eseguita su tutti i nodi h ( che sono n ) e per ogni coppia di nodi i e j ( che sono n2 )
Complessità totale: O(n3)
Si può verificare (per induzione su h) che l’algoritmo di Floyd-Warshall è esatto
E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 31
Esercizio Determinare i cammini minimi tra tutte le coppie di nodi del seguente grafo:
-7
4
1 3
2 48
53
3
410-2
