Enable JQuery execution.
Abilitare l'esecuzione di JQuery
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 F F C--F 5 C--G 6 E--G 4 F--G 3
 

Inizializzazione

Inserimento del nodo B nella frontiera
 
Frontiera:
B/0
 
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/0
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A999999   
B0  X
C999999   
D999999   
E999999   
F999999   
G999999   
 
Estrazione del nodo  B  a distanza 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 F F  999999  C--F 5 C--G 6 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 F F  999999  C--F 5 C--G 6 E--G 4 F--G 3
 
Frontiera:
A/8D/1E/9
Storico della frontiera:
B/0A/8D/1E/9
 
Ordine di visita dei nodi: [B]
 

Elaborazione di un nodo avente distanza minima, estratto dalla frontiera

Frontiera:
A/8D/1E/9
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A8B X
B0 SIX
C999999   
D1B X
E9B X
F999999   
G999999   
 
Estrazione del nodo  D  a distanza 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 F F  999999  C--F 5 C--G 6 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 F F  999999  C--F 5 C--G 6 E--G 4 F--G 3
 
Frontiera:
A/8E/9A/5
Storico della frontiera:
B/0A/8D/1E/9A/5
 
Ordine di visita dei nodi: [B, D]
 

Elaborazione di un nodo avente distanza minima, estratto dalla frontiera

Frontiera:
A/8E/9A/5
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5D X
B0 SIX
C999999   
D1BSIX
E9B X
F999999   
G999999   
 
Estrazione del nodo  A  a distanza 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 F F  999999  C--F 5 C--G 6 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 F F  999999  C--F 5 C--G 6 E--G 4 F--G 3
 
Frontiera:
A/8E/9C/15E/9G/7
Storico della frontiera:
B/0A/8D/1E/9A/5C/15E/9G/7
 
Ordine di visita dei nodi: [B, D, A]
 

Elaborazione di un nodo avente distanza minima, estratto dalla frontiera

Frontiera:
A/8E/9C/15E/9G/7
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSIX
B0 SIX
C15A X
D1BSIX
E9B X
F999999   
G7A X
 
Estrazione del nodo  G  a distanza 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 F F  999999  C--F 5 C--G 6 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 F F  10/G  C--F 5 C--G 6 E--G 4 F--G 3
 
Frontiera:
A/8E/9C/15E/9C/13E/9F/10
Storico della frontiera:
B/0A/8D/1E/9A/5C/15E/9G/7C/13E/9F/10
 
Ordine di visita dei nodi: [B, D, A, G]
 

Elaborazione di un nodo avente distanza minima, estratto dalla frontiera

Frontiera:
A/8E/9C/15E/9C/13E/9F/10
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSIX
B0 SIX
C13G X
D1BSIX
E9B X
F10G X
G7ASIX
 
Estrazione del nodo  A  a distanza 8
 
Il nodo A è già stato visitato, quindi lo ignoro
 

Elaborazione di un nodo avente distanza minima, estratto dalla frontiera

Frontiera:
E/9C/15E/9C/13E/9F/10
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSIX
B0 SIX
C13G X
D1BSIX
E9B X
F10G X
G7ASIX
 
Estrazione del nodo  E  a distanza 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 F F  10/G  C--F 5 C--G 6 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 F F  10/G  C--F 5 C--G 6 E--G 4 F--G 3
 
Frontiera:
C/15E/9C/13E/9F/10
Storico della frontiera:
B/0A/8D/1E/9A/5C/15E/9G/7C/13E/9F/10
 
Ordine di visita dei nodi: [B, D, A, G, E]
 

Elaborazione di un nodo avente distanza minima, estratto dalla frontiera

Frontiera:
C/15E/9C/13E/9F/10
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSIX
B0 SIX
C13G X
D1BSIX
E9BSIX
F10G X
G7ASIX
 
Estrazione del nodo  E  a distanza 9
 
Il nodo E è già stato visitato, quindi lo ignoro
 

Elaborazione di un nodo avente distanza minima, estratto dalla frontiera

Frontiera:
C/15C/13E/9F/10
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSIX
B0 SIX
C13G X
D1BSIX
E9BSIX
F10G X
G7ASIX
 
Estrazione del nodo  E  a distanza 9
 
Il nodo E è già stato visitato, quindi lo ignoro
 

Elaborazione di un nodo avente distanza minima, estratto dalla frontiera

Frontiera:
C/15C/13F/10
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSIX
B0 SIX
C13G X
D1BSIX
E9BSIX
F10G X
G7ASIX
 
Estrazione del nodo  F  a distanza 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 F F  10/G  C--F 5 C--G 6 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 F F  10/G  C--F 5 C--G 6 E--G 4 F--G 3
 
Frontiera:
C/15C/13C/13
Storico della frontiera:
B/0A/8D/1E/9A/5C/15E/9G/7C/13E/9F/10C/13
 
Ordine di visita dei nodi: [B, D, A, G, E, F]
 

Elaborazione di un nodo avente distanza minima, estratto dalla frontiera

Frontiera:
C/15C/13C/13
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSIX
B0 SIX
C13G X
D1BSIX
E9BSIX
F10GSIX
G7ASIX
 
Estrazione del nodo  C  a distanza 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 F F  10/G  C--F 5 C--G 6 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 F F  10/G  C--F 5 C--G 6 E--G 4 F--G 3
 
Frontiera:
C/15C/13
Storico della frontiera:
B/0A/8D/1E/9A/5C/15E/9G/7C/13E/9F/10C/13
 
Ordine di visita dei nodi: [B, D, A, G, E, F, C]
 

Elaborazione di un nodo avente distanza minima, estratto dalla frontiera

Frontiera:
C/15C/13
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSIX
B0 SIX
C13GSIX
D1BSIX
E9BSIX
F10GSIX
G7ASIX
 
Estrazione del nodo  C  a distanza 13
 
Il nodo C è già stato visitato, quindi lo ignoro
 

Elaborazione di un nodo avente distanza minima, estratto dalla frontiera

Frontiera:
C/15
 
Tabella:
NodoDistanzaPredecessoreVisitatoFrontiera
A5DSIX
B0 SIX
C13GSIX
D1BSIX
E9BSIX
F10GSIX
G7ASIX
 
Estrazione del nodo  C  a distanza 15
 
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 F F  10/G  C--F 5 C--G 6 E--G 4 F--G 3
 
 
 

Distanze minime dei nodi e relativi predecessori

NodoDistanzaPredecessoreVisitatoFrontiera
A5DSIX
B0 SIX
C13GSIX
D1BSIX
E9BSIX
F10GSIX
G7ASIX
 

Percorsi a costo minimo dal nodo B

B -> D -> A (5)
B (0)
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/0A/8D/1E/9A/5C/15E/9G/7C/13E/9F/10C/13
 

Ordine di visita dei nodi

[B, D, A, G, E, F, C]