Use an SVG enabled browser (eg Chrome, Firefox) for a proper visualization of the content.
See instructions here.
Per una corretta fruizione dei contenuti del sito deve essere utilizzato un browser abilitato alla visualizzazione di SVG (es. Chrome, Firefox).
Vedere le istruzioni qui.

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
 
Frontiera:
B
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A999999   
B0  X
C999999   
D999999   
E999999   
F999999   
G999999   

Elaborazione della frontiera finchè non è vuota

Elaborazione di un nodo avente distanza minima, estratto dalla frontiera

Frontiera:
B
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A999999   
B0  X
C999999   
D999999   
E999999   
F999999   
G999999   
 
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

Frontiera:
ADE
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A8B X
B0 SI 
C999999   
D1B X
E9B X
F999999   
G999999   
 
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

Frontiera:
AEA
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5D X
B0 SI 
C999999   
D1BSI 
E9B X
F999999   
G999999   
 
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

Frontiera:
EACEG
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSIX
B0 SI 
C15A X
D1BSI 
E9B X
F999999   
G7A 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

Frontiera:
ECEG
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSI 
B0 SI 
C15A X
D1BSI 
E9B X
F999999   
G7A 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

Frontiera:
ECECEF
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSI 
B0 SI 
C13G X
D1BSI 
E9B X
F10G X
G7ASI 
 
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

Frontiera:
CECEF
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSI 
B0 SI 
C13G X
D1BSI 
E9BSIX
F10G X
G7ASI 
 
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

Frontiera:
CCEF
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSI 
B0 SI 
C13G X
D1BSI 
E9BSIX
F10G X
G7ASI 
 
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

Frontiera:
CCF
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSI 
B0 SI 
C13G X
D1BSI 
E9BSI 
F10G X
G7ASI 
 
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

Frontiera:
CCC
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSI 
B0 SI 
C13G X
D1BSI 
E9BSI 
F10GSI 
G7ASI 
 
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

Frontiera:
CC
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSI 
B0 SI 
C13GSIX
D1BSI 
E9BSI 
F10GSI 
G7ASI 
 
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

Frontiera:
C
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSI 
B0 SI 
C13GSIX
D1BSI 
E9BSI 
F10GSI 
G7ASI 
 
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

NodoDistanzaPredecessoreVisitatoFrontiera
A5DSI 
B0 SI 
C13GSI 
D1BSI 
E9BSI 
F10GSI 
G7ASI 
 

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]