Distanze minime tra tutte le coppie nodi - Algoritmo di Bellman Ford
grafo
A
A
B
B
A--B
6
D
D
A--D
3
E
E
A--E
9
B--D
2
B--E
1
C
C
C--D
8
C--E
4
Matrice delle adiacenze
A B C D E A 0 6 0 3 9 B 6 0 0 2 1 C 0 0 0 8 4 D 3 2 8 0 0 E 9 1 4 0 0
Matrice delle distanze iniziale
A B C D E A 0/A 6/A 99/A 3/A 9/A B 6/B 0/B 99/B 2/B 1/B C 99/C 99/C 0/C 8/C 4/C D 3/D 2/D 8/D 0/D 99/D E 9/E 1/E 4/E 99/E 0/E
Passaggio 1
Passaggio 1: esamino il Nodo A
Miglioramento: da Nodo A a Nodo B via Nodo D distanza 5 rispetto a 6
A-B/D/5
Miglioramento: da Nodo A a Nodo C via Nodo D distanza 11 rispetto a 99
A-C/D/11
Miglioramento: da Nodo A a Nodo E via Nodo B distanza 6 rispetto a 9
A-E/B/6
Matrice delle distanze a seguito delle modifiche
A B C D E A 0/A 5/D
11/D
3/A 6/B
B 6/B 0/B 99/B 2/B 1/B C 99/C 99/C 0/C 8/C 4/C D 3/D 2/D 8/D 0/D 99/D E 9/E 1/E 4/E 99/E 0/E
Passaggio 1: esamino il Nodo B
Miglioramento: da Nodo B a Nodo A via Nodo D distanza 5 rispetto a 6
B-A/D/5
Miglioramento: da Nodo B a Nodo C via Nodo A distanza 16 rispetto a 99
B-C/A/16
Miglioramento: da Nodo B a Nodo C via Nodo D distanza 10 rispetto a 16
B-C/D/10
Miglioramento: da Nodo B a Nodo C via Nodo E distanza 5 rispetto a 10
B-C/E/5
Matrice delle distanze a seguito delle modifiche
A B C D E A 0/A 5/D 11/D 3/A 6/B B 5/D
0/B 5/E
2/B 1/B C 99/C 99/C 0/C 8/C 4/C D 3/D 2/D 8/D 0/D 99/D E 9/E 1/E 4/E 99/E 0/E
Passaggio 1: esamino il Nodo C
Miglioramento: da Nodo C a Nodo A via Nodo D distanza 11 rispetto a 99
C-A/D/11
Miglioramento: da Nodo C a Nodo B via Nodo A distanza 16 rispetto a 99
C-B/A/16
Miglioramento: da Nodo C a Nodo B via Nodo D distanza 10 rispetto a 16
C-B/D/10
Miglioramento: da Nodo C a Nodo B via Nodo E distanza 5 rispetto a 10
C-B/E/5
Miglioramento: da Nodo C a Nodo D via Nodo B distanza 7 rispetto a 8
C-D/B/7
Matrice delle distanze a seguito delle modifiche
A B C D E A 0/A 5/D 11/D 3/A 6/B B 5/D 0/B 5/E 2/B 1/B C 11/D
5/E
0/C 7/B
4/C D 3/D 2/D 8/D 0/D 99/D E 9/E 1/E 4/E 99/E 0/E
Passaggio 1: esamino il Nodo D
Miglioramento: da Nodo D a Nodo C via Nodo B distanza 7 rispetto a 8
D-C/B/7
Miglioramento: da Nodo D a Nodo E via Nodo A distanza 9 rispetto a 99
D-E/A/9
Miglioramento: da Nodo D a Nodo E via Nodo B distanza 3 rispetto a 9
D-E/B/3
Matrice delle distanze a seguito delle modifiche
A B C D E A 0/A 5/D 11/D 3/A 6/B B 5/D 0/B 5/E 2/B 1/B C 11/D 5/E 0/C 7/B 4/C D 3/D 2/D 7/B
0/D 3/B
E 9/E 1/E 4/E 99/E 0/E
Passaggio 1: esamino il Nodo E
Miglioramento: da Nodo E a Nodo A via Nodo B distanza 6 rispetto a 9
E-A/B/6
Miglioramento: da Nodo E a Nodo D via Nodo A distanza 9 rispetto a 99
E-D/A/9
Miglioramento: da Nodo E a Nodo D via Nodo B distanza 3 rispetto a 9
E-D/B/3
Matrice delle distanze a seguito delle modifiche
A B C D E A 0/A 5/D 11/D 3/A 6/B B 5/D 0/B 5/E 2/B 1/B C 11/D 5/E 0/C 7/B 4/C D 3/D 2/D 7/B 0/D 3/B E 6/B
1/E 4/E 3/B
0/E
Matrice delle distanze alla fine del passaggio 1
A B C D E A 0/A 5/D 11/D 3/A 6/B B 5/D 0/B 5/E 2/B 1/B C 11/D 5/E 0/C 7/B 4/C D 3/D 2/D 7/B 0/D 3/B E 6/B 1/E 4/E 3/B 0/E
Percorsi migliori tra i nodi alla fine del passaggio 1
A -> D -> B
A -> D -> B -> E -> C
A -> D
A -> D -> B -> E
B -> D -> A
B -> E -> C
B -> D
B -> E
C -> E -> B -> D -> A
C -> E -> B
C -> E -> B -> D
C -> E
D -> A
D -> B
D -> B -> E -> C
D -> B -> E
E -> B -> D -> A
E -> B
E -> C
E -> B -> D
Passaggio 2
Passaggio 2: esamino il Nodo A
Miglioramento: da Nodo A a Nodo C via Nodo B distanza 10 rispetto a 11
A-C/B/10
Matrice delle distanze a seguito delle modifiche
A B C D E A 0/A 5/D 10/B
3/A 6/B B 5/D 0/B 5/E 2/B 1/B C 11/D 5/E 0/C 7/B 4/C D 3/D 2/D 7/B 0/D 3/B E 6/B 1/E 4/E 3/B 0/E
Passaggio 2: esamino il Nodo B
Passaggio 2: esamino il Nodo C
Miglioramento: da Nodo C a Nodo A via Nodo B distanza 10 rispetto a 11
C-A/B/10
Matrice delle distanze a seguito delle modifiche
A B C D E A 0/A 5/D 10/B 3/A 6/B B 5/D 0/B 5/E 2/B 1/B C 10/B
5/E 0/C 7/B 4/C D 3/D 2/D 7/B 0/D 3/B E 6/B 1/E 4/E 3/B 0/E
Passaggio 2: esamino il Nodo D
Passaggio 2: esamino il Nodo E
Matrice delle distanze alla fine del passaggio 2
A B C D E A 0/A 5/D 10/B 3/A 6/B B 5/D 0/B 5/E 2/B 1/B C 10/B 5/E 0/C 7/B 4/C D 3/D 2/D 7/B 0/D 3/B E 6/B 1/E 4/E 3/B 0/E
Percorsi migliori tra i nodi alla fine del passaggio 2
A -> D -> B
A -> D -> B -> E -> C
A -> D
A -> D -> B -> E
B -> D -> A
B -> E -> C
B -> D
B -> E
C -> E -> B -> D -> A
C -> E -> B
C -> E -> B -> D
C -> E
D -> A
D -> B
D -> B -> E -> C
D -> B -> E
E -> B -> D -> A
E -> B
E -> C
E -> B -> D
Passaggio 3
Passaggio 3: esamino il Nodo A
Passaggio 3: esamino il Nodo B
Passaggio 3: esamino il Nodo C
Passaggio 3: esamino il Nodo D
Passaggio 3: esamino il Nodo E
Matrice delle distanze alla fine del passaggio 3
A B C D E A 0/A 5/D 10/B 3/A 6/B B 5/D 0/B 5/E 2/B 1/B C 10/B 5/E 0/C 7/B 4/C D 3/D 2/D 7/B 0/D 3/B E 6/B 1/E 4/E 3/B 0/E
Percorsi migliori tra i nodi alla fine del passaggio 3
A -> D -> B
A -> D -> B -> E -> C
A -> D
A -> D -> B -> E
B -> D -> A
B -> E -> C
B -> D
B -> E
C -> E -> B -> D -> A
C -> E -> B
C -> E -> B -> D
C -> E
D -> A
D -> B
D -> B -> E -> C
D -> B -> E
E -> B -> D -> A
E -> B
E -> C
E -> B -> D
Arresto
Nessuna modifica alle distanze minime, l'elaborazione può fermarsi
Percorsi ottimi tra i nodi
A -> D -> B
A -> D -> B -> E -> C
A -> D
A -> D -> B -> E
B -> D -> A
B -> E -> C
B -> D
B -> E
C -> E -> B -> D -> A
C -> E -> B
C -> E -> B -> D
C -> E
D -> A
D -> B
D -> B -> E -> C
D -> B -> E
E -> B -> D -> A
E -> B
E -> C
E -> B -> D
Matrice delle distanze ottime
A B C D E A 0/A 5/D 10/B 3/A 6/B B 5/D 0/B 5/E 2/B 1/B C 10/B 5/E 0/C 7/B 4/C D 3/D 2/D 7/B 0/D 3/B E 6/B 1/E 4/E 3/B 0/E
