UNIVERSITA' DEGLI STUDI DI BERGAMO Dipartimento di Ingegneria

INSTRADAMENTO: ALGORITMO DI

DIJKSTRA

FONDAMENTI DI RETI E TELECOMUNICAZIONE A.A. 2012/13 - II° Semestre

Esercizio 1 (Appello del 27/09/2002) Sia dato il grafo G=(N, A) pesato e non orientato riportato in figura. Applicando l’algoritmo di Dijkstra, calcolare il percorso a costo minimo da ogni nodo di N al nodo 3 (destinatario). Indicare con rigore i vari passi dell’algoritmo, utilizzando, se possibile, le notazioni usate a lezione.

Soluzione PASSO 0: valuto i nodi 2 – 5 –7 collegati con il nodo 3

S = {3}

1

5

2 3 4

82

7

1

3

6

7

9

2

1

4

2

102 =D

∞=01D

305 =D

2

1 5

6

∞=06D

907 =D

3

7

4

003 =D

∞=04D

1

3

9

PASSO 1: Scelgo il nodo 2, lo aggiungo all’insieme S e valuto il nodo 1 ad esso collegato S = {3, 2} PASSO 2: Scelgo il nodo 1, lo aggiungo all’insieme S e valuto i nodi 4 - 5 ad esso collegati S = {3, 2, 1}

1

2 4

5

6

7

1

2 3

9

311 =D

315 =D

∞=16D

917 =D

∞=14D

013 =D

112 =D

3

3

1

2 4

7

5

6

1

2

3

9

8

∞=26D

325 =D

323 =D

927 =D

1124 =D

023 =D

122 =D

PASSO 3: Scelgo il nodo 5, lo aggiungo all’insieme S e valuto il nodo 6 ad esso collegato S = {3, 2, 1, 5} PASSO 4: Scelgo il nodo 6, lo aggiungo all’insieme S e valuto i nodi 4 - 7 ad esso collegati S = {3, 2, 1, 5, 6}

2

1

3

5

6

4

7

331 =D

132 =D

033 =D

1134 =D

937 =D

536 =D

335 =D

1

3

9

8

2

2

1

2

3

6

7

3

142 =D

341 =D

947 =D

043 =D

5

4

2

2

1

9

1

644 =D

546 =D

345 =D

PASSO 5: Scelgo il nodo 4, lo aggiungo all’insieme S e valuto il nodo 7 ad esso collegato S = {3, 2, 1, 5, 6, 4} PASSO 6: Scelgo il nodo 7, lo aggiungo all’insieme S terminando il grafo S = {3, 2, 1, 5, 6, 4, 7}

1

2 3 4

6

5

3

1

2

2

1

7

2

053 =D

152 =D

351 =D

355 =D

556 =D

654 =D

857 =D

1

212

3

5

6

4

7

361 =D

162 =D

063 =D

664 =D

867 =D

566 =D

365 =D

2

1

3

1

2

2

PASSO 1: scelgo il nodo 7, lo aggiungo all’insieme S e valuto i nodi 4 – 6 ad esso collegati

S = {3, 7} PASSO 2: aggiungo il nodo 4 all’insieme S e valuto i nodi 6 – 5 ad esso collegati.

S = {3, 7, 4}

2

1

3 4

5 6

7

2

15

8

1

4

217 =D

314 =D

616 =D

1515 =D

812 =D

∞=11D

013 =D

3

2

1

5 6

7

4 1

2

15

8

3 10

227 =D

324 =D

023 =D

822 =D

∞=21D

1325 =D 62

6 =D

PASSO 3: aggiungo il nodo 6 all’insieme S e valuto i nodi 5 – 2 a lui collegati. S = {3, 7, 4, 6} PASSO 4: aggiungo il nodo 2 all’insieme S e valuto il nodo 1 a lui collegato S ={3, 7, 4, 6, 2}

5

2

3 4

1

5 6

7

2

1

8

3 237 =D

334 =D

033 =D

832 =D

∞=31D

636 =D113

5 =D

3

2

1

5 6

7

4 2

1

3

5

8

344 =D

247 =D

043 =D

842 =D

646 =D114

5 =D

1041 =D

2

PASSO 5: aggiungo il nodo 2 all’insieme S e valuto il nodo 1. S = {3, 7, 4, 6, 2, 1} PASSO 6: aggiungo il nodo 5 all’insieme S e ho finito di collegare tutti i nodi. S = {3, 7, 4, 6, 2, 1, 5}

3

2

1

4

7

5 6

656 =D115

5 =D

1051 =D

053 =D

257 =D

354 =D

852 =D

2

1

3

8

2

5

3

2

1

5 6

4

7

2

1

3

8

2

666 =D116

5 =D5

267 =D

1061 =D

862 =D

364 =D

063 =D

PASSO 1: Potrei scegliere sia il nodo 2 che il nodo 5. Scelgo il nodo 2, lo aggiungo all’insieme S e valuto i nodi 3 - 6 ad esso collegati S = {1,2} PASSO 2: Scelgo il nodo 5, lo aggiungo all’insieme S. S = {1,2,5}

212 =D

011 =D

215 =D

2 2

5

1

3

6

4

1014 =D

10

816 =D

6

8 1013 =D

2

222 =D

021 =D

225 =D

2 2

5

1

3

6

4

1024 =D

10

826 =D

6

1023 =D

2

8

PASSO 3: Scelgo il nodo 6, lo aggiungo all’insieme S. Valuto quindi i nodi collegati al nodo 5. S = {1,2,5,6} PASSO 4: Scelgo il nodo 3, lo aggiungo all’insieme S. S = {1,2,5,6,3}

2

10

242 =D

041 =D

245 =D

2 2

5

1

3

6

4

1044 =D

846 =D

6

1043 =D

2

8

1

2

5

3

4

6 2

235 =D

031 =D

232 =D

6

836 =D

8

1033 =D

1034 =D

10

PASSO 5: Scelgo il nodo 4, lo aggiungo all’insieme S. S = {1,2,5,6,3,4}

252 =D

051 =D

255 =D

2

2

5

1

3

6

4

1054 =D

856 =D

6

1053 =D

2

10

8

PASSO 1: Scelgo il nodo 2, lo aggiungo all’insieme S e valuto i nodi 3 - 5 ad esso collegati e il nodo 4 S={1,2} PASSO 2: Scelgo il nodo 5, lo aggiungo all’insieme S e valuto i nodi 3 - 4 ad esso collegati S={1,2,5}

1

1

1

122 =D

324 =D 22

5 =D

1

4

2

4

1

3

6

626 =D

323 =D

021 =D

5

4

112 =D

011 =D

414 =D 21

5 =D

1

3

2

4

3

5

6

∞=16D

413 =D

1 1

PASSO 3: Scelgo il nodo 3, lo aggiungo all’insieme S e valuto il nodo 4 e il nodo 6 ad esso collegato S={1,2,3,5} PASSO 4: Scelgo il nodo 4, lo aggiungo all’insieme S e valuto il nodo 6 S={1,2,3,4,5}

1

1

1

132 =D

334 =D 23

5 =D

1 2

2

4

1 6

536 =D

031 =D

5

3

333 =D

1

1

1

344 =D 24

5 =D

1 2

2

4

1 6

546 =D

041 =D

5

3

343 =D14

2 =D

PASSO 5: Scelgo il nodo 6 e lo aggiungo all’insieme S; tutti i nodi sono stati permanentemente etichettati: l’algoritmo è terminato. S={1,2,3,4,5,6}

1

1

1

354 =D 25

5 =D

1 2

2

4

1 6

556 =D

051 =D

5

3

353 =D15

2 =D

Passo 1: scelgo il nodo 4 poiché il più vicino, lo aggiungo all’insieme S e valuto i nodi 1 – 3 ad esso collegati S={6, 4} Passo 2: scelgo il nodo 3, lo aggiungo all’insieme S e valuto i nodi ad esso collegati: tutti i nodi hanno minor distanza da 6 se non si passa attraverso il nodo 3 S={6, 4, 3}

2 3

1

4

5 6

1

10 6

7

3

314 =D

612 =D

1311 =D 71

5 =D

413 =D

016 =D

2 3

1

4

5 6

1

10 6

7

3

026 =D132

1 =D

622 =D 42

3 =D

725 =D

324 =D

Passo 3: scelgo il nodo 6 perché il più vicino al nodo di destinazione, lo aggiungo all’insieme S e valuto il nodo 1 ad esso collegato S={6, 4, 3, 2} Passo 4: collego il nodo 5, lo aggiungo all’insieme S S={6, 4, 3, 2, 5}

2 3

1

4

5 6

2

1

6

7

3

735 =D

036 =D

433 =D 33

4 =D632 =D

831 =D

2 3

1

4

5 6

2

1

6

7

3

745 =D

841 =D

642 =D 44

3 =D 344 =D

046 =D

Passo 5 (passo finale): collego il nodo 1 e lo aggiungo all’insieme S S={6, 4, 3, 2, 5, 1}

2 3

1

4

5 6

2

1

6

7

3

755 =D

851 =D

652 =D 45

3 =D 354 =D

056 =D

PASSO 1: scelgo il nodo 2, lo aggiungo all’insieme S e valuto i nodi 3 e 6 ad esso collegati S = {1,2} PASSO 2: scelgo il nodo 5, lo aggiungo all’insieme S e valuto il nodo 6 ad esso collegato, non considero il collegamento 5-3 perché risulterebbe più costoso di 31

3 =D S = {1,2,5}

7

5

4

011 =D

21

2 =D

215 =D

1116 =D

∞=17D

1514 =D31

3 =D

6

3

1

2

7

4

021 =D

222 =D

225 =D

926 =D

∞=27D

1524 =D32

3 =D

6

3 2

5

1

PASSO 3: scelgo il nodo 3, lo aggiungo all’insieme S e valuto il nodo 7 ad esso collegato S = {1,2,5,3} PASSO 4: scelgo il nodo 7, lo aggiungo all’insieme S e valuto il nodo 4 ad esso collegato, non considero il collegamento 7-6 perché risulterebbe ugualmente costoso a 93

6 =D S = {1,2,5,3,7}

7

4

031 =D

232 =D

235 =D

936 =D

537 =D

1534 =D33

3 =D

6

3 2

5

1

7

4

041 =D

242 =D

245 =D

946 =D

547 =D

644 =D34

3 =D

6

3 2

5

1

PASSO 5: scelgo il nodo 4, lo aggiungo all’insieme S, non vi sono nodi ad esso collegati da considerare. S = {1,2,5,3,7,4} PASSO 5: scelgo il nodo 6, lo aggiungo all’insieme S, non vi sono altri nodi da considerare, abbiamo ottenuto il percorso a costo minimo. S = {1,2,5,3,7,4,6}

7

4

051 =D

252 =D

255 =D

956 =D

557 =D

654 =D35

3 =D

6

3 2

5

1

7

4

061 =D

262 =D

265 =D

966 =D

567 =D

664 =D36

3 =D

6

3 2

5

1