Distanze minime tra tutte le coppie nodi - Algoritmo di Bellman Ford
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 |