Post on 02-May-2015
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