Reti di Calcolatori - Tabella di instradamento del nodo A con algoritmo di Dijkstra

Algoritmo del percorso ottimo

Si parte dal nodo d'origine A che entra subito a far parte dell'insieme N = {A}. Partendo dal nodo A, i collegamenti diretti sono:

• A-C:1
• A-D:2
• A-B:5

A-C non è migliorabile, quindi C entra nell'insieme N sicché N = {A, C} mentre il nodo tiene memorizzati i percorsi A-D:2 e A-B:5 per confrontarli con altri percorsi successivi.

Collegamenti dal nodo C

Partendo, adesso, dal nodo C, i collegamenti diretti a nodi che non appartengono all'insieme N sono:

• C-D:5
• C-G:9

Quindi ho:

• A-C-D:6
• A-C-G:10

che vengono aggiunti ai percorsi già in memoria e confrontati per determinare il percorso ottimo.

Confronto dei percorsi

Se l'algoritmo trova in memoria 2 o più percorsi diversi tra loro che partono dal nodo sorgente A e giungono allo stesso nodo finale, li confronta e determina quello a costo minimo che resta in memoria provvisoria mentre gli altri vengono cancellati.

In memoria il nodo A ha:

• A-D:2
• A-B:5
• A-C-D:6
• A-C-G:10

in cui A-D è quello migliore, cioè quello a costo minimo, quindi entra nell'insieme N sicché N = {A, C, D}. A-C-D viene cancellato perché ha costo maggiore di A-D.