i j u , c b b Determinare con l`algoritmo dei cammini minimi

Determinare con l’algoritmo dei cammini minimi successivi (SSPT)
il flusso di costo minimo sul grafo
–5
2, 7
1
0
2
3, 1
–5
3
5, 3
4, 3
4
,
1
0
5
3, 1
4, 1
4,
0
3, 1
3
4
7
6
2, −4
uij, cij
bi
i
j
bj
Dati del problema
i bi
1 −5
2
0
3 −5
4
3
5
0
6
7
(i, j)
(1, 4)
(1, 5)
(2, 1)
(2, 4)
(2, 5)
(3, 2)
(3, 4)
(3, 6)
(5, 4)
(5, 6)
uij
2
5
3
1
3
3
4
2
4
4
cij
7
3
1
4
1
1
0
−4
3
1
Algoritmo dei cammini minimi successivi : inizializzazione
Pseudoflusso minimale x1 iniziale :
non esistendo archi
con costo negativo e capacità infinita,
uno pseudoflusso minimale iniziale
si ottiene ponendo
xij = 0 se cij ≥ 0
xij = uij se cij < 0
(i, j)
(1, 4)
(1, 5)
(2, 1)
(2, 4)
(2, 5)
(3, 2)
(3, 4)
(3, 6)
(5, 4)
(5, 6)
uij
2
5
3
1
3
3
4
2
4
4
cij
7
3
1
4
1
1
0
−4
3
1
xij
0
0
0
0
0
0
0
2
0
0
Calcolo degli sbilanciamenti ai nodi nello pseudoflusso x1
i
1
2
3
4
5
6
BS FS bi ei = BS − FS −bi
0
0 −5
5
0
0
0 0
0 −2 −5
3
0
0 3
−3
0
0
0 0
2
0 7
−5
nodi con eccedenza di flusso : O(x1) = { 1, 3 }
nodi con difetto di flusso :
D(x1) = { 4, 6 }
sbilanciamento complessivo : g(x1) = 5 + 3 = 8 ≠ 0
ei(x1) i
5
xij
0
1
4
0
0
2
ej(x1)
−3
0
0
0
j
5
0
0
0
0
0
3
3
2
6
−5
nodi con eccedenza di flusso : O(x1) = { 1, 3 }
nodi con difetto di flusso : D(x1) = { 4, 6 }
sbilanciamento complessivo : g(x1) = 5 + 3 = 8 ≠ 0
⇒ occorre eseguire la procedura Trova-Cammino-Minimo
⇒ per trovare un cammino aumentante di costo minimo P
⇒ da un nodo s ∈ O(x1) ad un nodo t ∈ D(x1)
grafo G con pseudoflusso x1
(i, j)
(1, 4)
(1, 5)
(2, 1)
(2, 4)
(2, 5)
(3, 2)
(3, 4)
(3, 6)
(5, 4)
(5, 6)
xij
0
0
0
0
0
0
0
2
0
0
uij
2
5
3
1
3
3
4
2
4
4
cij
7
3
1
4
1
1
0
−4
3
1
grafo residuo G(x1)
(i, j) uij′
(1, 4) 2
(1, 5) 5
(2, 1) 3
(2, 4) 1
(2, 5) 3
(3, 2) 3
(3, 4) 1
(5, 4) 4
(5, 6) 4
(6, 3) 2
cij′
7
3
1
4
1
1
0
3
1
4
Grafo residuo G’(x1) associato allo pseudoflusso x1 iniziale:
7
1
4
nello pseudoflusso iniziale gli archi di G
o sono vuoti o sono saturi :
3 quindi nel grafo residuo G(x ) vi è
1
uno e un solo arco per ogni arco di G
5
• concorde all’arco di G e con costo cij′ = cij
se l’arco di G è vuoto
1
3
1
4
2
1
0
1
3
6
4
i
• discorde all’arco di G e con costo cij′ = −cij
se l’arco di G è saturo
cij′
j
Essendo | O(x1) | = 2, si introduce una super-radice r = 0
collegata a tutti i nodi in O(x1) con archi a costo nullo:
il grafo residuo ampliato G’(x1) è
7
1
3
0
0
3
1
4
0
2
4
5
1
1
0
1
3
4
6
Tutti gli archi di G’(x1) hanno costo nonnegativo:
i cammini minimi si determinano con l’algoritmo di Dijkstra
Archi del grafo residuo ampliato
archi
(0, 1)
(0, 3)
(1, 4)
(1, 5)
(2, 1)
(2, 4)
(2, 5)
(3, 2)
(3, 4)
(5, 4)
(5, 6)
(6, 3)
costi
0
0
7
3
1
4
1
1
0
3
1
4
Esecuzione dell’algoritmo di Dijkstra su tabella
L’insieme Q è formato dai nodi i il cui costo di è circolettato.
In Q si sceglie il nodo u il cui costo du è il minimo dei di :
⇒ si copia du senza circoletto sulla riga dell’iterazione in corso
Archi v della stella uscente da u :
⇒ si leggono nell’elenco degli archi del grafo (ordinati per nodo di coda)
Per ogni v, se du + cuv < dv :
⇒ si scrive il nuovo dv circolettato in riga corrente e colonna del nodo v
Differenze
algoritmo in pseudocodice :
se il nodo v di cui si è aggiornato il costo dv è già presente in Q,
esso non viene (ovviamente) inserito in Q
algoritmo su tabella :
il costo dv che è stato aggiornato viene circolettato in ogni caso,
anche se era già circolettato (e non scelto) nella riga precedente
Inizializzazione
d
nodi
iter. 0 1 2 3 4 5 6
0
0 M M M M M M
Q={0}
p
iter 0 1
0 nil 0
nodi
2 3 4
0 0 0
5 6
0 0
Iterazione 1
d
nodi
iter. 0 1 2 3 4 5 6
0
0 M M M M M M
1
0 0
0
Q = { 1, 3 }
p
iter 0 1
0 nil 0
1
0
nodi
2 3 4
0 0 0
0
5 6
0 0
si parte dal nodo 0,
ma si percorrono gli archi di G
e non gli archi fittizi
Iterazione 2
d
nodi
iter. 0 1 2 3 4 5 6
0
0 M M M M M M
1
0 0
0
2
0
7 3
Q = { 3, 4, 5 }
p
iter 0 1
0 nil 0
1
0
2
nodi
2 3 4
0 0 0
0
1
5 6
0 0
1
Iterazione 3
d
nodi
iter 0 1 2 3
0 0 M M M
1 0 0
0
2
0
3
1 0
4 5 6
M M M
7
0
3
Q = { 2, 4, 5 }
p
iter 0 1
0 nil 0
1
0
2
3
nodi
2 3 4
0 0 0
0
1
3
3
5 6
0 0
1
Iterazione 4
d
nodi
iter 0 1 2 3
0 0 M M M
1 0 0
0
2
0
3
1 0
4
4 5 6
M M M
7
0
0
Q = { 2, 5 }
3
p
iter 0 1
0 nil 0
1
0
2
3
4
nodi
2 3 4
0 0 0
0
1
3
3
5 6
0 0
1
Iterazione 5
d
nodi
iter 0 1 2 3
0 0 M M M
1 0 0
0
2
0
3
1 0
4
5
1
4 5 6
M M M
7
0
0
3
2
Q={5}
p
iter 0 1
0 nil 0
1
0
2
3
4
5
nodi
2 3 4
0 0 0
0
1
3
3
5 6
0 0
1
2
Iterazione 6
d
nodi
iter 0 1 2 3
0 0 M M M
1 0 0
0
2
0
3
1 0
4
5
1
6
4 5 6
M M M
7
0
0
3
2
2 3
Q={6}
p
iter 0 1
0 nil 0
1
0
2
3
4
5
6
nodi
2 3 4
0 0 0
0
1
3
3
5 6
0 0
1
2
5
Iterazione 7
d
nodi
iter 0 1 2 3
0 0 M M M
1 0 0
0
2
0
3
1 0
4
5
1
6
7
4 5 6
M M M
7
0
0
3
2
2 3
3
p
iter 0 1
0 nil 0
1
0
2
3
4
5
6
7
Q = ∅ : l’algoritmo di Dijkstra termina
nodi
2 3 4
0 0 0
0
1
3
3
5 6
0 0
1
2
5
Albero dei cammini minimi sul grafo residuo ampliato
d1 = 0
1
d0 = 0
0
4
d4 = 0
5
d5 = 2
6
d6 = 3
d2 = 1
2
3
d3 = 0
Albero dei cammini minimi sul grafo residuo
d1 = 0
1
4
d4 = 0
5
d5 = 2
6
d6 = 3
d2 = 1
2
3
d3 = 0
cammino 3 – 4 : di costo 0
cammino 3 – 2 – 5 – 6 : di costo 3
Inviamo il flusso aggiuntivo lungo il cammino 3 – 4 .
Capacità del cammino 3 – 4:
θ(P, x1) = u34 – x34 = 4 – 0 = 4
Quantità θ di flusso aggiuntivo che si può inviare da s = 3 a t = 4 :
θ = min { θ(P, x1) , e3(x1) , – e4(x1) } = min { 4 , 3 , –(–3) } = 3
Si ottiene lo pseudoflusso x2 rappresentato in figura
bi , ei
i
3, 0
–5,5
0
1
0
4
3–0–3=0
0
0
0
0, 0 2
5
0
0
3
0
0 – (– 5) – 5 = 0
xij
3
– 5, 0
2
6
7, – 5
0, 0
j
bj , ej
nodi con eccedenza di flusso : O(x2) = { 1 }
nodi con difetto di flusso : D(x2) = { 6 }
sbilanciamento complessivo : g(x2) = 5 ≠ 0
Occorre trovare un cammino aumentante P di costo minimo
dal nodo 1 al nodo 6
grafo G con pseudoflusso x2
(i, j)
(1, 4)
(1, 5)
(2, 1)
(2, 4)
(2, 5)
(3, 2)
(3, 4)
(3, 6)
(5, 4)
(5, 6)
xij
0
0
0
0
0
0
3
2
0
0
uij
2
5
3
1
3
3
4
2
4
4
cij
7
3
1
4
1
1
0
−4
3
1
grafo residuo G(x2)
(i, j) uij′
(1, 4) 2
(1, 5) 5
(2, 1) 3
(2, 4) 1
(2, 5) 3
(3, 2) 3
(3, 4) 1
(4, 3) 3
(5, 4) 4
(5, 6) 4
(6, 3) 2
cij′
7
3
1
4
1
1
0
0
3
1
4
ei(x)
uij’, cij’
i
j
5
2, 7
1
5, 3
0 3
5
0
3,
0
3, 1
1,
0
3, 1
0
Su questo grafo si deve determinare
il cammino di costo minimo
tra il nodo 1 (unico elemento di O(x2))
4
1,
2
4
4, 3
3, 1
0
ej(x)
2, 4
4, 1
e il nodo 6 (unico elemento di D(x2)).
Poiché tutti i costi sono nonnegativi,
si usa l’algoritmo di Dijkstra
6
–5
dati del problema SPT
7
1
3
4
3
1
4
2
5
1
1
0
0
1
3
4
6
(i, j)
(1, 4)
(1, 5)
(2, 1)
(2, 4)
(2, 5)
(3, 2)
(3, 4)
(4, 3)
(5, 4)
(5, 6)
(6, 3)
cij′
7
3
1
4
1
1
0
0
3
1
4
Inizializzazione
d
nodi
iter. 1 2 3 4 5 6
0
0 M M M M M
Q={1}
p
nodi
iter. 1 2 3 4 5 6
0 nil 1 1 1 1 1
Iterazione 1
d
nodi
iter. 1 2 3 4 5 6
0
0 M M M M M
1
0
7
3
Q = { 4, 5 }
p
nodi
iter. 1 2 3 4 5 6
0 nil 1 1 1 1 1
1
1 1
si parte dal nodo 1,
ma si percorrono gli archi di G’
e non gli archi fittizi
Iterazione 2
d
nodi
iter. 1 2 3 4 5 6
0
0 M M M M M
1
2
0
7
6
3
3 4
Q = { 4, 6 }
p
nodi
iter. 1 2 3 4 5 6
0 nil 1 1 1 1 1
1
1 1
2
5
5
Iterazione 3
d
nodi
iter. 1 2 3 4 5 6
0
0 M M M M M
1
2
3
0
7
6
8
Q = { 3, 4 }
3
3 4
4
p
nodi
iter. 1 2 3 4 5 6
0 nil 1 1 1 1 1
1
1 1
2
5
5
3
6
Iterazione 4
d
nodi
iter. 1 2 3 4 5 6
0
0 M M M M M
1
2
3
4
0
7
6
8
6
6
Q={3}
3
3 4
4
p
nodi
iter. 1 2 3 4 5 6
0 nil 1 1 1 1 1
1
1 1
2
5
5
3
6
4
4
Iterazione 5
d
nodi
iter. 1 2 3 4 5 6
0
0 M M M M M
1
2
3
4
5
0
7
6
7
8
6
6
Q={2}
6
3
3 4
4
p
nodi
iter. 1 2 3 4 5 6
0 nil 1 1 1 1 1
1
1 1
2
5
5
3
6
4
4
5
3
Iterazione 6
d
nodi
iter. 1 2 3 4 5 6
0
0 M M M M M
1
2
3
4
5
6
0
7
6
7
7
8
6
6
6
3
3 4
4
p
nodi
iter. 1 2 3 4 5 6
0 nil 1 1 1 1 1
1
1 1
2
5
5
3
6
4
4
5
3
6
Q = ∅ : l’algoritmo di Dijkstra termina
Albero dei cammini minimi
d1 = 0
1
4
d2 = 7 2
d3 = 6
3
d4 = 6
5
d5 = 3
6
d6 = 4
Il cammino di costo minimo dal nodo 1 al nodo 6 ha costo 4
Inviamo il flusso aggiuntivo lungo il cammino 1 – 5, 5 – 6 .
Capacità del cammino 1 – 5, 5 – 6 :
θ(P, x2) = min {u15 – x15 , u56 – x56 } = min {5 , 4} = 4
Quantità θ di flusso aggiuntivo che si può inviare da s = 1 a t = 6 :
θ = min { θ(P, x2) , e1(x2) , – e6(x2) } = min {4, 5, –(–5) } = 4
Si ottiene lo pseudoflusso x3 rappresentato in figura
bi , ei
–5,1
0
2
4
5
0
4
3
0
0 – (– 5) – 5 = 0
3–0–3=0
0
0
0, 0
i
3, 0
0
4
1
xij
3
– 5, 0
2
6
7, – 1
0, 0
j
bj , ej
Calcolo degli sbilanciamenti ai nodi nello pseudoflusso x3
nodo entrata – uscita – deficit
1
0
–4
5
1
2
0
0
0
0
3
0
– (3+2)
5
0
4
3
0
–3
0
5
4
–4
0
0
6
2+4
0
–7
–1
nodi con eccedenza di flusso : Ox = { 1 }
nodi con difetto di flusso : Dx = { 6 }
sbilanciamento complessivo : g(x) = 1 ≠ 0
Occorre trovare un cammino aumentante di costo minimo P
dal nodo 1 al nodo 6
Si costruisce il grafo residuo Gx associato allo pseudoflusso x2 :
1
0, 2, 7
1
4,
5,
0, 3, 1
2
4
j
i
4
0
0, 4, 3
5
0
0
4, 4, 1
3, 1
0
2
3, 1
0 3
2, 2, -4
0 3
6
–1
ex(j)
j
2, 7
1
3,
0, 3, 1
uij’, cij’
5
0, 3, 1
4,
0
1,
,
0
3
ex(i)
1, 3
4,
–3
4
,
1
4
0
4, 3
5
0
3, 1
0
i
ex(j)
3,
xij, uij, cij
1,
0
ex(i)
2, 4
4, –1
6
–5
Determinare l’albero dei cammini minimi a partire dal nodo 1
Vi sono costi sono negativi: algoritmo di Bellman
cij’
i
7
1
3
–3
1
4
3
4
2
j
5
1
–1
0
0
1
3
4
6
Inizializzazione
d1 = 0
1
2
d2 = M
3
d3 = M
4
d4 = M
5
d5 = M
6
d6 = M
Q={1}
Iterazione 1: da Q si sceglie il nodo 1, Q = ∅
FS (1) = { (1, 4), (1, 5) }
• d1 + c14 = 0 + 7 < M = d4
⇒
d4 = 7 e Q = { 4 }
• d1 + c15 = 0 + 3 < M = d5
⇒
d5 = 3 e Q = { 4, 5 }
d1 = 0
1
2
d2 = M
d3 = M
3
4
d4 = 7
5
d5 = 3
6
d6 = M
Q = { 4, 5 }
Iterazione 2: da Q si sceglie il nodo 4, Q = { 5 }
FS (4) = { (4, 3) }
• d4 + c43 = 7 + 0 < M = d3
⇒
d3 = 7 e Q = { 5, 3 }
d1 = 0
1
4
d4 = 7
2
d2 = M
5
d5 = 3
3
6
d6 = M
d3 = 7
Q = { 5, 3 }
Iterazione 3: da Q si sceglie il nodo 5, Q = { 3 }
FS (5) = { (5, 4) }
• d5 + c54 = 3 + 3 < 7 = d4
⇒
d4 = 6 e Q = { 3, 4 }
d1 = 0
1
4
d4 = 6
2
d2 = M
5
d5 = 3
3
6
d6 = M
d3 = 7
Q = { 3, 4 }
Iterazione 4: da Q si sceglie il nodo 3, Q = { 4 }
FS (3) = { (3, 2), (3, 4) }
• d3 + c32 = 7 + 1 < M = d2
⇒
d2 = 8 e Q = {4, 2 }
• d3 + c34 = 7 + 0 > 6 = d4
d1 = 0
d2 = 8
d3 = 7
1
4
d4 = 6
2
5
d5 = 3
3
6
d6 = M
Q ={ 4, 2 }
Iterazione 5: da Q si sceglie il nodo 4, Q = { 2 }
FS (4) = { (4, 3) }
• d4 + c43 = 6 + 0 < 7 = d3
d1 = 0
d2 = 8
d3 = 6
⇒
d3 = 6 e Q = {2, 3 }
1
4
d4 = 6
2
5
d5 = 3
3
6
d6 = M
Q = { 2, 3 }
Iterazione 6: da Q si sceglie il nodo 2, Q = { 3 }
FS (2) = { (2, 1), (2, 4), (2, 5) }
• d2 + c21 = 8 + 1 > 0 = d1
• d2 + c24 = 8 + 4 > 6 = d4
• d2 + c25 = 8 + 1 > 3 = d5
d1 = 0
d2 = 8
d3 = 6
1
4
d4 = 6
2
5
d5 = 3
3
6
d6 = M
Q={3}
Iterazione 7: da Q si sceglie il nodo 3, Q = ∅
FS (3) = { (3, 2), (3, 4) }
• d3 + c32 = 6 + 1 < 8 = d2 ⇒
d2 = 7 e Q = { 2 }
• d3 + c34 = 6 + 0 = 6 = d4
d1 = 0
d2 = 7
d3 = 6
1
4
d4 = 6
2
5
d5 = 3
3
6
d6 = M
Q={2}
Iterazione 8: da Q si sceglie il nodo 2, Q = ∅
FS (2) = { (2, 1), (2, 4), (2, 5) }
• d2 + c21 = 7 + 1 > 0 = d1
• d2 + c24 = 7 + 4 > 6 = d4
• d2 + c25 = 7 + 1 > 3 = d5
d1 = 0
d2 = 7
d3 = 6
1
4
d4 = 6
2
5
d5 = 3
3
6
d6 = M
Q=∅
L’algoritmo di Bellman è terminato senza trovare un cammino
dal nodo 1 al nodo 6
Il nodo 6, rispetto al grafo residuo associato allo pseudoflusso x2 ,
non è connesso.
Il problema di flusso di costo minimo
(che stavamo risolvendo con SSPT)
non ha soluzione ammissibile.