Problema: cammini minimi da tutti i vertici
a tutti i vertici
Dato un grafo pesato G =(V,E,w), trovare un cammino
minimo tra ogni coppia di vertici.
Applicazione dei metodi di programmazione
dinamica.
Master Bioinformatica 2002: Grafi
Sviluppo di un algoritmo di
programmazione dinamica
• Caratterizzazione della struttura di una soluzione
ottima
• definizione ricorsiva del valore di una soluzione
ottima.
• Calcolo iterativo del valore di una soluzione
ottima mediante una strategia bottom-up
• Costruzione di una soluzione ottima a partire dal
valore calcolato
Master Bioinformatica 2002: Grafi
Cammino minimo
Peso di un cammino p = <v1,…,vk>
w(p) = k-1i=1 w(vi, vi+1)
Il peso di un cammino minimo da u a v è definito come
d(u,v) = min{w(p) | p: u
=0
=
v } se v è raggiungibile da u
se v = u
se v non è raggiungibile da u
Master Bioinformatica 2002: Grafi
I pesi w degli archi sono valori interi, possono essere
anche valori negativi. Assumiamo che il grafo non
contenga cicli con pesi negativi, perchè in questo
caso la nozione di cammino minimo non è ben
definita
-5
b
a
2
c
3
Percorrendo il ciclo svariate volte otteniamo un cammino con
un peso sempre piu’ basso
Master Bioinformatica 2002: Grafi
Rappresentazione con matrice di adiacenza
Assumiamo che un grafo (orientato) pesato G =
(V,E,w) con |V| = n sia rappresentato con una
matrice di adiacenza n  n W[i,j] definita come
W[i,j] = 0
= w(i,j)
=
se i = j
se i  j e (i,j)  E
se (i,j)  E
Master Bioinformatica 2002: Grafi
Struttura dei cammini minimi
Proprietà della sottostruttura ottima: sia p un
cammino ottimo: ogni sottocammino di p e’ ottimo.
pij
p
v0
vj
vi
qij
vk
Il sottocammino pij di p deve essere un cammino ottimo da vi a vj
Master Bioinformatica 2002: Grafi
Vertici intermedi
Sia p = <v1,v2…,vl> un cammino semplice da v1a,vl
i vertici intermedi sono v2,…,vl-1.
Siano V = {1,…,n} i vertici di un grafo G, considera
per un vertice k arbitrario il sottoinsieme
{1,…,k}
siano i,j  V.
Master Bioinformatica 2002: Grafi
Algoritmo di Floyd-Warshall
Considera tutti i cammini da i a j in cui vertici
intermedi sono nell’insieme {1,…,k} e sia p un
cammino minimo tra di essi.
E’ possibile definire una relazione tra p e i cammini
minimi tra i vertici i e j i cui vertici intermedi sono
nell’insieme
{1,…,k-1}
Master Bioinformatica 2002: Grafi
• Se k non e’ un vertice intermedio di p, allora tutti
i vertici intermedi di p sono nell’insieme
{1,…,k-1}.
Questo significa che il peso di un cammino
minimo da i a j in cui tutti i vertici intermedi sono
in {1,…,k} è dato dal peso di un cammino minimo
da i a j in cui tutti i vertci intermedi sono in
{1,…,k-1}.
Master Bioinformatica 2002: Grafi
• Se k è un vertice intermedio di p allora possiamo
spezzare p così:
j
i
p1
k
p2
• p1 e’ un cammino minimo da i a k in cui tutti i vertici intermedi
sono nell’insieme {1,…,k-1}.
• p2 e’ un cammino minimo da i a k in cui tutti i vertici intermedi
sono nell’insieme {1,…,k-1}.
Master Bioinformatica 2002: Grafi
Questo significa che il peso di un cammino
minimo da i a j in cui tutti i vertici intermedi sono
in {1,…,k} è dato dal peso di un cammino minimo
da i a k in cui tutti i vertci intermedi sono in
{1,…,k-1} + il peso di un cammino minimo da k
a j in cui tutti i vertci intermedi sono in {1,…,k-1}.
Master Bioinformatica 2002: Grafi
Relazione di ricorrenza
Definiamo
D(k) [i,j] = peso di un cammino minimo da i a j in
cui tutti i vertici intermedi sono
nell’insieme {1,…k}
Master Bioinformatica 2002: Grafi
D(k) [i,j] = W[i,j]
se k = 0
D(k) [i,j] = min {D(k-1) [i,j], D(k-1) [i,k]+ D(k-1)[k,j]}
se k > 0
Master Bioinformatica 2002: Grafi
Sottoproblemi comuni
D(5)[1,6]
D(4)[1,6]
D(4)[1,5] + D(4)[5,6]
D(3)[1,6] D(3)[1,4] + D(3)[4,6]
D(3)[1,5]
D(3)[5,6] D(3)[5,4] + D(3)[4,6]
D(3)[1,4] + D(3)[4,5]
Master Bioinformatica 2002: Grafi
Calcolo iterativo della sequenza di matrici
D(0),…, D(n)
Floyd-Warshall(W) //W matrice di adiacenza n  n
D(0)  W
for k = 1 to n
for i = 1 to n
for j = 1 to n
D(k) [i,j]  min{D(k-1)[i,j], D(k-1)[i,k] + D(k-1)[k,j]}
return D(n)
Complessità: O(n3)
Master Bioinformatica 2002: Grafi
Calcolo dei cammini minimi
Matrice dei predecessori
P(k) [i,j] = predecessore di j in un cammino minimo
da i a j in cui tutti i vertici intermedi sono
nell’insieme {1,…,k}.
i
x
P(k) [i,j] = x
Master Bioinformatica 2002: Grafi
j
Relazione di ricorrenza per i predecessori
• per k = 0
P(k)[i,j] = NULL se i = j oppure W[i,j]= 
P(k)[i,j] = i
se i  j e W[i,j] < 
• per k > 0
P(k)[i,j] = P(k-1)[i,j]
se D[i,j](k-1) D [i,k](k-1) + D[k,j](k-1)
P(k)[i,j] = P(k-1)[k,j]
se D[i,j](k-1) > D [i,k](k-1) + D[k,j](k-1)
Master Bioinformatica 2002: Grafi
Calcolo delle matrici D(0),…, D(n) e P(0),…, P(n)
Floyd-Warshall(W)
Inizializza D(0) e P(0) mediante W
for k = 1 to n
for i = 1 to n
for j = 1 to n
D(k) [i,j]  D(k-1)[i,j]
P(k) [i,j]  P(k-1)[i,j]
if D(k) [i,j] > D (k-1) [i,k] + D(k-1)[k,j]
then D(k) [i,j]  D (k-1) [i,k]+ D(k-1)[k,j]
P(k) [i,j]  P(k-1)[k,j]
return <D(n), P(n) >
Master Bioinformatica 2002: Grafi
Esempio
W
-3
2
5
4
4
5
3
1
2
3
1
2
3
4
Master Bioinformatica 2002: Grafi
1
0



2
5
0

-3
3
2
3
0

4

4
5
0
D(0)
1
2
3
4
1
0



2
5
0

-3
3
2
3
0

P(0)
4

4
5
0
1
2
3
4
1
N
N
N
N
2
1
N
N
4
D(1)
1
2
3
4
1
0



2
5
0

-3
3
2
3
0

3
1
2
N
N
4
N
2
3
N
P(1)
4

4
5
0
1
2
3
4
1
N
N
N
N
Master Bioinformatica 2002: Grafi
2
1
N
N
4
3
1
2
N
N
4
N
2
3
N
D(1)
1
2
3
4
1
0



2
5
0

-3
3
2
3
0

P(1)
4

4
5
0
1
2
3
4
1
N
N
N
N
2
1
N
N
4
D(2)
1
2
3
4
1
0



2
5
0

-3
3
2
3
0
0
3
1
2
N
N
4
N
2
3
N
P(2)
4
9
4
5
0
1
2
3
4
1
N
N
N
N
Master Bioinformatica 2002: Grafi
2
1
N
N
4
3
1
2
N
2
4
2
2
3
N
D(2)
1
2
3
4
1
0



2
5
0

-3
3
2
3
0
0
P(2)
4
9
4
5
0
1
2
3
4
1
N
N
N
N
2
1
N
N
4
D(3)
1
2
3
4
1
0



2
5
0

-3
3
2
3
0
0
3
1
2
N
2
4
2
2
3
N
P(3)
4
7
4
5
0
1
2
3
4
1
N
N
N
N
Master Bioinformatica 2002: Grafi
2
1
N
N
4
3
1
2
N
2
4
3
2
3
N
D(3)
1
2
3
4
1
0



2
5
0

-3
3
2
3
0
0
P(3)
4
7
4
5
0
1
2
3
4
1
N
N
N
N
2
1
N
N
4
D(4)
1
2
3
4
1
0



2
4
0
2
-3
3
2
3
0
0
3
1
2
N
2
4
3
2
3
N
P(4)
4
7
4
5
0
1
2
3
4
1
N
N
N
N
Master Bioinformatica 2002: Grafi
2
4
N
4
4
3
1
2
N
2
4
3
2
3
N
-3
2
5
4
4
1
1
2
3
4
5
3
3
2
1
N
N
N
N
2
4
N
4
4
3
1
2
N
2
-3
2
4
4
4
2
5
1
2
3
1
Master Bioinformatica 2002: Grafi
3
3
4
3
2
3
N
-3
2
5
4
4
5
3
1
1
2
3
4
2
3
-3
2
1
N
N
N
N
2
4
N
4
4
3
1
2
N
2
4
3
2
3
N
-3
2
4
4
5
1
3
1
Master Bioinformatica 2002: Grafi
3
3