Lezioni di Ricerca Operativa
Corso di Laurea in Informatica ed Informatica Applicata
Università di Salerno
Lezione n° 21: 25-26 Maggio 2009
Problema dell’albero dei cammini minimi
Anno accademico 2008/2009
Prof. Cerulli – Dott.ssa Gentili
Il problema dei cammini minini
G=(N,A)
sorgente
cij = costo dell’arco (i,j)
xij = variabili decisionali
p
7
1
15
5
69
44
xij =
se xijp
0
se xijp
21
4
1
21
7
1
8
7
35
9
10
3
11
28
5
40
2
9
6
1
destinazione
Modello matematico
7
1
2
15
9
5
69
44
21
4
21
5
7
1
8
7
35
9
10
3
11
28
6
1
40
Modello matematico
7
1
15
9
5
69
44
21
4
21
5
1
7
1
8
7
35
9
10
3
11
28
6
40
2
Modello matematico
7
1
15
9
5
69
44
21
4
21
5
1
11
28
6
40
2
7
1
8
7
35
Il problema dei cammini minini (varianti)
 Uno ad uno
 Uno a tutti
 Tutti a tutti
Il problema dei cammini minini
G=(N,A)
sorgente
T
7
1
15
9
5
69
44
21
4
21
5
1
7
1
8
7
35
9
10
3
11
28
6
40
2
Etichette dei nodi
G=(N,A)
d1
7
1
9
d5 5
69
44
15
d4
21
4
35
1
7
d7
1
8
7
d9
9
10
3
11
21
5
40
2
28
6
d6
d2
d8
d3
Algoritmo prototipo
Passo 1: Inizializzazione.
ds=0, Ps=NULL, dk=, Pk=s kN\{s},
Q={s};
Passo 2: Estrai un vertice x da Q (Q= Q \{x}) ed
aggiorna quando possibile le etichette dei
vertici in FS(x):
yFS(x) se dx + cxy < dy allora
dy = dx + cxy , Py= x e se y Q inseriscilo in
Q (Q= Q  {y}) (test di ottimalità)
Aggioramento delle etichette
yFS(x) se dx + cxy < dy allora dy = dx + cxy e Py= x
 x=4, y=5
d4 + c45 < d5 ?
d5 = d4 + c45 e P5= 4
 x=4, y=2
d4 + c42 < d2 ?
…………………
 x=4, y=9
d4 + c49 < d9 ?
d9 = d4 + c49 e P9= 4
5
42
36
2
18
9
67
55
15
21
7
4
34
Algoritmo prototipo
Passo 1: Inizializzazione.
ds=0, Ps=NULL, dk=, Pk=s kN\{s},
Q={s};
Passo 2: Estrai un vertice x da Q (Q= Q \{x}) ed
aggiorna quando possibile le etichette dei
vertici in FS(x):
yFS(x) se dx + cxy < dy allora
dy = dx + cxy , Py= x e se y Q inseriscilo
in Q (Q= Q  {y}) (test di ottimalità)
Passo 3: Fino a quando Q 
 ripeti il passo 2 ;
Differenti implementazioni
Gli algoritmi per l’SPT si distinguono per:
– La politica di estrazione del nodo da Q
(label setting e label correcting)
– La struttura dati utilizzata per implementare Q
Algoritmo di Dijkstra (label setting)
Dijkstra (G,s)
Inizializzazione;
( ds=0, Ps=NULL, dk=, Pk=s kN\{s} , Q={s})
while ( Q  ){
x = Extract_min(Q);
Test_ottimalità(x,y);
}
con yFS(x);
L’algoritmo di Dijkstra (label setting)
G=(N,A)
0
7
1
9
9

5
69

7

44
2
15

21
4
21
5
35
1
7

10

1
8
7
Q
9
3
11
28
6
40


2
5
2
1
7
9
0
7
L’algoritmo di Dijkstra (label setting)
G=(N,A)
0
7
1
9
9
5
69

7
44
2
15

22
21
4
21
5
35
1
7

10

42
1
8
7
Q
9
3
11
28
6
40
47


4
5
3
4
2
9
3
5
9
22
9
42
22
47
42
7
9
47
L’algoritmo di Dijkstra (label setting)
G=(N,A)
0
7
1
9
9
5
69
7
44
2
15
22
21
4
21
5
35
1
7

10
42
1
8
7
Q
9
3
11
28
78
 6
40
47

5
6
4
4
3
3
9
6
9
78
9
22
22
42
47
42
78
47
L’algoritmo di Dijkstra (label setting)
G=(N,A)
0
7
1
9
9
5
69
78
50
7
44
2
15
22
21
4
21
5
1
7
43

1
8
7
35

33
Q
9
10
3
11
28
6
40
47
42
8
7
3
8
4
7
3
9
6
43
33
42
33
22
43
42
47
78
50
L’algoritmo di Dijkstra (label setting)
G=(N,A)
0
7
1
9
9
5
69
50
7
44
2
15
22
21
4
21
5
1
7
43
1
8
7
35
33
Q
9
10
3
11
28
6
40
47
42
34
8
3
7
9
6
33
42
34
43
47
50
L’algoritmo di Dijkstra (label setting)
G=(N,A)
0
7
1
9
9
5
69
50
7
44
2
15
22
21
4
21
5
1
7
43
10
34
1
8
7
35
Q
9
3
11
28
6
40
47
44
33
3
7
9
6
34
43
47
44
50
L’algoritmo di Dijkstra (label setting)
G=(N,A)
0
7
1
9
9
5
69
50
48
7
44
2
15
22
21
4
21
5
1
7
43
10
34
1
8
7
35
Q
9
3
11
28
6
40
44
33
7
9
6
43
44
50
48
Il problema dei cammini minini
T
7
1
15
9
5
69
44
21
4
21
5
1
7
8
7
35
9
10
3
11
28
6
40
2
1
Albero dei Cammini minimi  albero
di copertura minimo
SPT=22
5
2
0
5
10
4
6
1
7
11
3
7
15
Albero dei Cammini minimi  albero
di copertura minimo
SPT=22
MST=21
5
2
0
5
10
6
1
7
15
5
2
10
4
1
11
3
7
4
6
7
11
3