Algoritmo di Dijkstra

Giuseppe Inturri

Università di Catania

Corso di Laurea in Ingegneria per l’Ambiente ed il Territorio

2006

Fondamenti di Ingegneria dei Sistemi di Trasporto

Esempio di algoritmo di Dijkstra

1

4 5

2 3

6

0

7

1

2

4

2

6

23

1

P = {}, T = {1, 2, 3, 4, 5, 6}

Esempio di algoritmo di Dijkstra

1

4 5

2 3

6

0

7

1

2

4

2

6

23

1

4

7P = {1}, T = {2, 3, 4, 5, 6}

Esempio di algoritmo di Dijkstra

1

4 5

2 3

6

0

7

1

2

4

2

6

23

1

4

7

6

5

4

P = {1,4}, T = {2, 3, 5, 6}

Esempio di algoritmo di Dijkstra

1

4 5

2 3

6

0

7

1

2

4

2

6

23

1

7 5

4 6

5

11

P = {1,4,3}, T = {2, 5, 6}

Esempio di algoritmo di Dijkstra

1

4 5

2 3

6 11

0

7

1

2

4

2

6

23

1

7 5

4 6

5

6

9

P = {1,4,3,5}, T = {2, 6}

Esempio di algoritmo di Dijkstra

1

4 5

2 3

6 11

0

7

1

2

4

2

6

23

1

7 5

4 6

5

6

9

7P = {1,4,3,5,2}, T = {6}

Esempio di algoritmo di Dijkstra

1

4 5

2 3

6 11

0

7

1

2

4

2

6

23

1

5

4 6

5

6

9

7

9

P = {1,4,3,5,2,6}, T = {}

Albero dei percorsi minimi

1

4 5

2 3

6 11

0

7

1

2

4

2

6

23

1

5

4 6

5

6

9

7

9