Post on 02-May-2015
Lezione n° 19: 12-13 Maggio 2008
Problema dell’albero dei cammini minimi
Anno accademico 2007/2008
Prof. Cerulli – Dott.ssa Gentili
Lezioni di Ricerca OperativaCorso di Laurea in Informatica ed Informatica Applicata
Università di Salerno
Il problema dei cammini minini
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
sorgente
1128
940
10
21
cij = costo dell’arco (i,j)
xij = variabili
decisionali
xij
=
1 se xijp
0 se xijp
destinazione
p
Modello matematico1
5
6
4
7
2
3
8
9
69
44
7
1
35
5
7
1
21
15
1128
940
10
21
Modello matematico
1
5
6
4
7
2
3
8
9
69
44
7
1
35
5
7
1
21
15
1128
940
10
21
Modello matematico
1
5
6
4
7
2
8
9
69
44
7
1
35
5
7
1
21
15
1128
40
21
Il problema dei cammini minini (varianti)
Uno ad uno
Uno a tutti
Tutti a tutti
Il problema dei cammini minini
1
5
6
4
7
2
3
8
9
69
44
7
1
35
5
7
1
21
15
sorgente
1128
940
10
21
T
G=(N,A)
Etichette dei nodi
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
1128
940
10
21
d1 d2 d9
d5
d6
d7
d8
d3
d4
Algoritmo prototipoPasso 1: Inizializzazione.
ds=0, Ps=NULL, dk=, Pk=s kN\{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):
yFS(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
5
9
427
34
15
42
67
18
21
yFS(x) se dx + cxy < dy allora dy = dx + cxy e Py= x
x=4, y=5d4 + c45 < d5 ?d5 = d4 + c45 e P5= 4
x=4, y=2d4 + c42 < d2 ?
…………………
x=4, y=9d4 + c49 < d9 ?d9 = d4 + c49 e P9= 4
36
55
Algoritmo prototipoPasso 1: Inizializzazione.
ds=0, Ps=NULL, dk=, Pk=s kN\{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):
yFS(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 ;
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
Differenti implementazioni
Dijkstra (G,s)
Inizializzazione; ( ds=0, Ps=NULL, dk=, Pk=s kN\{s} , Q={s})
while ( Q ){ x = Extract_min(Q); Test_ottimalità(x,y); con yFS(x);
}
Algoritmo di Dijkstra (label setting)
79512
L’algoritmo di Dijkstra (label setting)
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
1128
940
10
21
0 Q
7
9
2 7
0
247
95
9
7
L’algoritmo di Dijkstra (label setting)
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
1128
940
10
21
0 Q
47
42
22
9
747
3 42
4 22
9
5 9
3 42
4 22
6478
47
9
7
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
1128
940
10
21
0 Q
42
22
9
9
3 42
4 22
5
47
78
93 42
22
6
47
78
L’algoritmo di Dijkstra (label setting)
4878
47
9
7
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
1128
940
10
21
0 Q
42
22
33
43
50
9
42
22
6
47
78
3
7 43
33
50
73 42
8 33
43
L’algoritmo di Dijkstra (label setting)
47
9
7
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
1128
940
10
21
0 Q
42
22
33
43
50
34
96
47
50
73 42
8 33
43
34
L’algoritmo di Dijkstra (label setting)
34
34
47
9
7
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
1128
940
10
21
0 Q
22
33
43
50
96
47
50
73
43
44
44
L’algoritmo di Dijkstra (label setting)
4344
44
349
7
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
1128
940
10
21
0 Q
22
3350
96 50
7 43
48
48
L’algoritmo di Dijkstra (label setting)
Il problema dei cammini minini
1
5
6
4
7
2
3
8
9
69
44
7
1
35
5
7
1
21
15
1128
940
10
21
T
Albero dei Cammini minimi albero di copertura minimo
1
2
3
5
7
6
0
5
7
4
10
11
15
SPT=22
Albero dei Cammini minimi albero di copertura minimo
1
2
3
5
7
6
0
5
7
4
10
11
15
1
2
3
5
7
64
10
11
MST=21
SPT=22