Algoritmo di Dijkstra Giuseppe Inturri Università di Catania Corso di Laurea in Ingegneria per...
9
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
Transcript of Algoritmo di Dijkstra Giuseppe Inturri Università di Catania Corso di Laurea in Ingegneria per...
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
