Cammini minimi
tra tutte le
coppie
1/13
Cammini minimi tra tutte le coppie
Dato un grafo (orientato o non orientato) G = (V,E)
con funzione di peso w: E  R, trovare per ogni coppia
di vertici u,v  V il minimo peso di un cammino da u a v.
Verrà calcolata anche una matrice di predecessori
(uv) dove uv è NIL se u=v o se non c’è un cammino
da u a v, altrimenti è un predecessore di v su di un
cammino minimo da u.
Il sottografo indotto dall’i-esima riga della matrice 
sarà un albero di cammini minimi con radice in i.
2/13
Algoritmo di Floyd-Warshall
E’ un algoritmo di programmazione dinamica, può
gestire archi di peso negativo ma si assume che non ci
siano cicli negativi.
Idea:
ds,t(i): cammino minimo da s a t contenente solo i
vertici intermedi v1, ..., vi
ds,t(0) = w(s,t)
3/13
Algoritmo di Floyd-Warshall: idea
ds,t(i): cammino minimo da s a t contenente solo i vertici
intermedi v1, ..., vi
ds,t(0) = w(s,t)
ds,t(k) =
w(s,t)
if k = 0
min{ds,t(k-1), ds,k(k-1) + dk,t(k-1)}
if k > 0
4/13
Algoritmo di Floyd-Warshall
Floyd-Warshall(W)
1 n=rows[W]
2 D(0)=W
3 for k = 1 to n do
2
for i = 1 to n do
3
for j = 1 to n do
4
dij(k) = min(dij(k-1), dik(k-1) + dkj(k-1))
5 return D(n)
5/13
Algoritmo di Floyd-Warshall:
esempio
W
3
1
2
7
4
8
2
-4
5
0
1
6
4
3

-5

2

3
0
4


8

1

0 
-5 0
 6
-4
7


0
6/13
Algoritmo di Floyd-Warshall:
esempio
(0)
D(0)
0
3
8


2
0
4

0 
-5 0
 6




1
-4
1
1
7


0
1
2
2
3
4
4
5
7/13
Algoritmo di Floyd-Warshall:
esempio
(1)
D(1)
0
3
8


2
0
4
5



0 
-5 0
 6

1
-4
1
1
7

-2
0
1
2
4
3
1
4
2
1
5
8/13
Algoritmo di Floyd-Warshall:
esempio
(2)
D(2)
0
3
8
4
-4


2
0
4
5


 1
0 5
-5 0
 6
7
11
-2
0
1
4
3
1
1
2
1
2
2
2
2
1
4
5
9/13
Algoritmo di Floyd-Warshall:
esempio
(3)
D(3)
0
3
4
-4


2
0  1
4 0 5
-1 -5 0
  6
7
11
-2
0

8
1
4
3
3
1
2
1
2
2
2
2
1
4
5
10/13
Algoritmo di Floyd-Warshall:
esempio
(4)
D(4)
0
3
-1 4
-4
3
7
2
8
0
4
-1
5
-4
0
-5
1
-1
3
-2
0
1
5
0
6
1
4
4
4
4
3
3
3
4
2
1
4
2
2
1
1
1
4
4
5
11/13
Algoritmo di Floyd-Warshall:
esempio
(5)
D(5)
0
3
-3 2
-4
3
7
2
8
0
4
-1
5
-4
0
-5
1
-1
3
-2
0
1
5
0
6
1
4
4
4
4
3
3
3
4
5
1
4
2
2
1
1
1
4
4
5
12/13
Algoritmo di Floyd-Warshall:
complessità
Determinata dei tre cicli for.
Ogni esecuzione dell’istruzione interna è O(1), quindi:
T(V,E) = (n3) = (V3)
13/13