Ricerca del percorso minimo e algoritmo di Dijkstra

Il problema del percorso minimo

La ricerca del percorso minimo serve a trovare, tra un router di partenza e uno di destinazione, il tragitto con il costo totale minore. Il costo di un collegamento è il peso dell'arco e può dipendere da larghezza di banda, latenza, affidabilità e costo economico imposto dal provider. Come un navigatore GPS, i router analizzano la mappa della rete con algoritmi matematici; tra i più noti c'è l'algoritmo di Dijkstra.

Come lavora Dijkstra

L'algoritmo calcola il percorso più breve da un singolo nodo verso tutti gli altri. All'inizio il costo del nodo di partenza è $0$, mentre gli altri valgono $\infty$. A ogni passo si sceglie il nodo non visitato con costo attuale minore, si esaminano i vicini e si aggiorna la tabella solo se il nuovo costo è strettamente minore del precedente. La formula di aggiornamento è:

• $D(v)$: costo registrato per raggiungere $v$;
• $D(u)$: costo minimo confermato per $u$;
• $c(u,v)$: peso del collegamento tra $u$ e $v$.

Risultato

Il nodo scelto viene marcato come visitato definitivamente e il processo si ripete finché tutti i nodi sono visitati. Alla fine si ottiene un albero dei cammini minimi, che indica al router su quale porta inoltrare ogni pacchetto.