Cammini a costo minimo partendo dal nodo B - Algoritmo di Dijkstra
grafo
A
A
B
B
A--B
8
C
C
A--C
10
D
D
A--D
4
E
E
A--E
5
G
G
A--G
2
B--D
1
B--E
9
C--G
6
F
F
C--F
5
E--G
4
F--G
3
Inizializzazione
Inserimento del nodo B nella frontiera
Tabella:
Nodo Distanza Predecessore Visitato Frontiera A 999999 B 0 X C 999999 D 999999 E 999999 F 999999 G 999999
Elaborazione della frontiera finchè non è vuota
Elaborazione di un nodo avente distanza minima, estratto dalla frontiera
Tabella:
Nodo Distanza Predecessore Visitato Frontiera A 999999 B 0 X C 999999 D 999999 E 999999 F 999999 G 999999
Estrazione del nodo B
a distanza minima 0
Visita del nodo B
grafo
A
A
999999
B
B
0
A--B
8
C
C
999999
A--C
10
D
D
999999
A--D
4
E
E
999999
A--E
5
G
G
999999
A--G
2
B--D
1
B--E
9
C--G
6
F
F
999999
C--F
5
E--G
4
F--G
3
Aggiorno la distanza del nodo adiacente non ancora visitato A, da 999999 a 8, segnando come predecessore B
A/8/B
Inserimento nella frontiera del nodo adiacente non ancora visitato A
Aggiorno la distanza del nodo adiacente non ancora visitato D, da 999999 a 1, segnando come predecessore B
D/1/B
Inserimento nella frontiera del nodo adiacente non ancora visitato D
Aggiorno la distanza del nodo adiacente non ancora visitato E, da 999999 a 9, segnando come predecessore B
E/9/B
Inserimento nella frontiera del nodo adiacente non ancora visitato E
grafo
A
A
8/B
B
B
0
A--B
8
C
C
999999
A--C
10
D
D
1/B
A--D
4
E
E
9/B
A--E
5
G
G
999999
A--G
2
B--D
1
B--E
9
C--G
6
F
F
999999
C--F
5
E--G
4
F--G
3
Storico della frontiera: [B, A, D, E]
Ordine di visita dei nodi: [B]
Elaborazione di un nodo avente distanza minima, estratto dalla frontiera
Tabella:
Nodo Distanza Predecessore Visitato Frontiera A 8 B X B 0 SI C 999999 D 1 B X E 9 B X F 999999 G 999999
Estrazione del nodo D
a distanza minima 1
Visita del nodo D
grafo
A
A
8/B
B
B
0
A--B
8
C
C
999999
A--C
10
D
D
1/B
A--D
4
E
E
9/B
A--E
5
G
G
999999
A--G
2
B--D
1
B--E
9
C--G
6
F
F
999999
C--F
5
E--G
4
F--G
3
Aggiorno la distanza del nodo adiacente non ancora visitato A, da 8 a 5, segnando come predecessore D
A/5/D
Inserimento nella frontiera del nodo adiacente non ancora visitato A
grafo
A
A
5/D
B
B
0
A--B
8
C
C
999999
A--C
10
D
D
1/B
A--D
4
E
E
9/B
A--E
5
G
G
999999
A--G
2
B--D
1
B--E
9
C--G
6
F
F
999999
C--F
5
E--G
4
F--G
3
Storico della frontiera: [B, A, D, E, A]
Ordine di visita dei nodi: [B, D]
Elaborazione di un nodo avente distanza minima, estratto dalla frontiera
Tabella:
Nodo Distanza Predecessore Visitato Frontiera A 5 D X B 0 SI C 999999 D 1 B SI E 9 B X F 999999 G 999999
Estrazione del nodo A
a distanza minima 5
Visita del nodo A
grafo
A
A
5/D
B
B
0
A--B
8
C
C
999999
A--C
10
D
D
1/B
A--D
4
E
E
9/B
A--E
5
G
G
999999
A--G
2
B--D
1
B--E
9
C--G
6
F
F
999999
C--F
5
E--G
4
F--G
3
Aggiorno la distanza del nodo adiacente non ancora visitato C, da 999999 a 15, segnando come predecessore A
C/15/A
Inserimento nella frontiera del nodo adiacente non ancora visitato C
Inserimento nella frontiera del nodo adiacente non ancora visitato E
Aggiorno la distanza del nodo adiacente non ancora visitato G, da 999999 a 7, segnando come predecessore A
G/7/A
Inserimento nella frontiera del nodo adiacente non ancora visitato G
grafo
A
A
5/D
B
B
0
A--B
8
C
C
15/A
A--C
10
D
D
1/B
A--D
4
E
E
9/B
A--E
5
G
G
7/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
999999
C--F
5
E--G
4
F--G
3
Storico della frontiera: [B, A, D, E, A, C, E, G]
Ordine di visita dei nodi: [B, D, A]
Elaborazione di un nodo avente distanza minima, estratto dalla frontiera
Tabella:
Nodo Distanza Predecessore Visitato Frontiera A 5 D SI X B 0 SI C 15 A X D 1 B SI E 9 B X F 999999 G 7 A X
Estrazione del nodo A
a distanza minima 5
Il nodo A è già stato visitato, quindi lo ignoro
Elaborazione di un nodo avente distanza minima, estratto dalla frontiera
Tabella:
Nodo Distanza Predecessore Visitato Frontiera A 5 D SI B 0 SI C 15 A X D 1 B SI E 9 B X F 999999 G 7 A X
Estrazione del nodo G
a distanza minima 7
Visita del nodo G
grafo
A
A
5/D
B
B
0
A--B
8
C
C
15/A
A--C
10
D
D
1/B
A--D
4
E
E
9/B
A--E
5
G
G
7/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
999999
C--F
5
E--G
4
F--G
3
Aggiorno la distanza del nodo adiacente non ancora visitato C, da 15 a 13, segnando come predecessore G
C/13/G
Inserimento nella frontiera del nodo adiacente non ancora visitato C
Inserimento nella frontiera del nodo adiacente non ancora visitato E
Aggiorno la distanza del nodo adiacente non ancora visitato F, da 999999 a 10, segnando come predecessore G
F/10/G
Inserimento nella frontiera del nodo adiacente non ancora visitato F
grafo
A
A
5/D
B
B
0
A--B
8
C
C
13/G
A--C
10
D
D
1/B
A--D
4
E
E
9/B
A--E
5
G
G
7/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
10/G
C--F
5
E--G
4
F--G
3
Storico della frontiera: [B, A, D, E, A, C, E, G, C, E, F]
Ordine di visita dei nodi: [B, D, A, G]
Elaborazione di un nodo avente distanza minima, estratto dalla frontiera
Tabella:
Nodo Distanza Predecessore Visitato Frontiera A 5 D SI B 0 SI C 13 G X D 1 B SI E 9 B X F 10 G X G 7 A SI
Estrazione del nodo E
a distanza minima 9
Visita del nodo E
grafo
A
A
5/D
B
B
0
A--B
8
C
C
13/G
A--C
10
D
D
1/B
A--D
4
E
E
9/B
A--E
5
G
G
7/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
10/G
C--F
5
E--G
4
F--G
3
grafo
A
A
5/D
B
B
0
A--B
8
C
C
13/G
A--C
10
D
D
1/B
A--D
4
E
E
9/B
A--E
5
G
G
7/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
10/G
C--F
5
E--G
4
F--G
3
Storico della frontiera: [B, A, D, E, A, C, E, G, C, E, F]
Ordine di visita dei nodi: [B, D, A, G, E]
Elaborazione di un nodo avente distanza minima, estratto dalla frontiera
Tabella:
Nodo Distanza Predecessore Visitato Frontiera A 5 D SI B 0 SI C 13 G X D 1 B SI E 9 B SI X F 10 G X G 7 A SI
Estrazione del nodo E
a distanza minima 9
Il nodo E è già stato visitato, quindi lo ignoro
Elaborazione di un nodo avente distanza minima, estratto dalla frontiera
Tabella:
Nodo Distanza Predecessore Visitato Frontiera A 5 D SI B 0 SI C 13 G X D 1 B SI E 9 B SI X F 10 G X G 7 A SI
Estrazione del nodo E
a distanza minima 9
Il nodo E è già stato visitato, quindi lo ignoro
Elaborazione di un nodo avente distanza minima, estratto dalla frontiera
Tabella:
Nodo Distanza Predecessore Visitato Frontiera A 5 D SI B 0 SI C 13 G X D 1 B SI E 9 B SI F 10 G X G 7 A SI
Estrazione del nodo F
a distanza minima 10
Visita del nodo F
grafo
A
A
5/D
B
B
0
A--B
8
C
C
13/G
A--C
10
D
D
1/B
A--D
4
E
E
9/B
A--E
5
G
G
7/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
10/G
C--F
5
E--G
4
F--G
3
Inserimento nella frontiera del nodo adiacente non ancora visitato C
grafo
A
A
5/D
B
B
0
A--B
8
C
C
13/G
A--C
10
D
D
1/B
A--D
4
E
E
9/B
A--E
5
G
G
7/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
10/G
C--F
5
E--G
4
F--G
3
Storico della frontiera: [B, A, D, E, A, C, E, G, C, E, F, C]
Ordine di visita dei nodi: [B, D, A, G, E, F]
Elaborazione di un nodo avente distanza minima, estratto dalla frontiera
Tabella:
Nodo Distanza Predecessore Visitato Frontiera A 5 D SI B 0 SI C 13 G X D 1 B SI E 9 B SI F 10 G SI G 7 A SI
Estrazione del nodo C
a distanza minima 13
Visita del nodo C
grafo
A
A
5/D
B
B
0
A--B
8
C
C
13/G
A--C
10
D
D
1/B
A--D
4
E
E
9/B
A--E
5
G
G
7/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
10/G
C--F
5
E--G
4
F--G
3
grafo
A
A
5/D
B
B
0
A--B
8
C
C
13/G
A--C
10
D
D
1/B
A--D
4
E
E
9/B
A--E
5
G
G
7/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
10/G
C--F
5
E--G
4
F--G
3
Storico della frontiera: [B, A, D, E, A, C, E, G, C, E, F, C]
Ordine di visita dei nodi: [B, D, A, G, E, F, C]
Elaborazione di un nodo avente distanza minima, estratto dalla frontiera
Tabella:
Nodo Distanza Predecessore Visitato Frontiera A 5 D SI B 0 SI C 13 G SI X D 1 B SI E 9 B SI F 10 G SI G 7 A SI
Estrazione del nodo C
a distanza minima 13
Il nodo C è già stato visitato, quindi lo ignoro
Elaborazione di un nodo avente distanza minima, estratto dalla frontiera
Tabella:
Nodo Distanza Predecessore Visitato Frontiera A 5 D SI B 0 SI C 13 G SI X D 1 B SI E 9 B SI F 10 G SI G 7 A SI
Estrazione del nodo C
a distanza minima 13
Il nodo C è già stato visitato, quindi lo ignoro
grafo
A
A
5/D
B
B
0
A--B
8
C
C
13/G
A--C
10
D
D
1/B
A--D
4
E
E
9/B
A--E
5
G
G
7/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
10/G
C--F
5
E--G
4
F--G
3
Distanze minime dei nodi e relativi predecessori
Nodo Distanza Predecessore Visitato Frontiera A 5 D SI B 0 SI C 13 G SI D 1 B SI E 9 B SI F 10 G SI G 7 A SI
Percorsi a costo minimo dal nodo B
B -> D -> A (5)
B -> D -> A -> G -> C (13)
B -> D (1)
B -> E (9)
B -> D -> A -> G -> F (10)
B -> D -> A -> G (7)
Storico della frontiera
[B, A, D, E, A, C, E, G, C, E, F, C]
Ordine di visita dei nodi
[B, D, A, G, E, F, C]
