Nella teoria dei grafi, una delle pietre miliari di questa branca è senza dubbio il grande lavoro svolto da Dijkstra. L’argomento è consigliato nella disciplina di informatica del quarto anno degli istituti tecnici.
Commentiamo un esempio come il seguente con 7 nodi e 9 lati, ognuno etichettato con un lettera E* e un numero dopo la virgola indicante il peso. In questo caso il grafo non è orientato ma le considerazioni che possiamo fare non sarebbero molto diverse. Vogliamo trovare il percorso minimo tra i nodi A e G.
Step 0: su ogni nodo assegniamo il valore infinito tranne il nodo di partenza A e preapariamo la matrice per tenere traccia dei vari step.
| Nodi | B | C | D | E | F | G | |
| step 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | |
| step 1 | |||||||
| step 2 | |||||||
| step 3 | |||||||
| step 4 | |||||||
| step 5 | |||||||
| step 6 |
Step 1: seleziono il nodo A (in rosso), visito tutti i nodi adiacenti che non siano già stati visitati, quindi B e C che hanno ancora peso infinito. Aggiorno il nodo inserendo il peso del nodo precedente, in questo caso A con 0 più il peso dei rami da cui siamo passati.
| Nodi | B | C | D | E | F | G | |
| step 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | |
| step 1 | A | 5,A | 3,A | ∞ | ∞ | ∞ | ∞ |
| step 2 | |||||||
| step 3 | |||||||
| step 4 | |||||||
| step 5 | |||||||
| step 6 |
Step 2: conclusa la visita dal nodo A, lo contrassegno in grigetto per indicarlo come analizzato e non serve più tenerlo in considerazione. E’ il momento di riguardare tutti i nostri nodi e scegliere il nodo con il numero più basso, tenendo conto che infinito è il massimo invece. Scegliamo il nodo C e procediamo a visitare tutti i nodi adiacenti: A lo abbiamo già gestito, non serve tornare indietro, visitiamo D e E.
| Nodi | B | C | D | E | F | G | |
| step 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | |
| step 1 | A | 5,A | 3,A | ∞ | ∞ | ∞ | ∞ |
| step 2 | AC | 7,C | 4,C | ∞ | ∞ | ||
| step 3 | |||||||
| step 4 | |||||||
| step 5 | |||||||
| step 6 |
Step 3: andiamo a scegliere il successivo nodo con peso più basso, quindi il nodo E. visitiamo tutti i nodi adiacenti D e G. D è stato già visitato in percedenza assumendo il peso 3, quindipssando da E avremmo 4+3=7 che è maggiore del 3 già presente. Non aggiorniamo quindi nessun valore, annoto giusto con un cancelletto/simbolo qualsiasi che ho comunque analizzato il nodo. G invece non è stato visitato precedentemente quindi assume il valore 4+7=11. Sono arrivato al nodo finale, ma non so se abbiamo trovato il percorso migliore. Bisogna continuare ad analizzare tutti i nodi restanti.
| Nodi | B | C | D | E | F | G | |
| step 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | |
| step 1 | A | 5,A | 3,A | ∞ | ∞ | ∞ | ∞ |
| step 2 | AC | 7,C | 4,C | ∞ | ∞ | ||
| step 3 | ACE | # | 11,E | ||||
| step 4 | |||||||
| step 5 | |||||||
| step 6 |
Step 4: tra tutti i nodi quello con il peso minore non visitato è B. Da qui solo un nodo non è stato bloccato, il D, ma per raggiungerlo da B abbiamo 5 presente+2 del lato = 7 che è guale al 7 già presente sul nodo D. Non aggiorno nulla, mi annoto solo che ho analizzato il nodo.
| Nodi | B | C | D | E | F | G | |
| step 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | |
| step 1 | A | 5,A | 3,A | ∞ | ∞ | ∞ | ∞ |
| step 2 | AC | 7,C | 4,C | ∞ | ∞ | ||
| step 3 | ACE | 11,E | |||||
| step 4 | ACEB | # | |||||
| step 5 | |||||||
| step 6 |
Step 5: prossimo nodo da analizzare D. I suoi adiacenti non bloccati è solo F che ha ancora infinito, quindi aggiorno il suo valore 7+6=13 passando da D.
| Nodi | B | C | D | E | F | G | |
| step 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | |
| step 1 | A | 5,A | 3,A | ∞ | ∞ | ∞ | ∞ |
| step 2 | AC | 7,C | 4,C | ∞ | ∞ | ||
| step 3 | ACE | 11,E | |||||
| step 4 | ACEB | # | |||||
| step 5 | ACEBD | 13,D | |||||
| step 6 |
Step 6: Tra i nodi rimangono G con 11 e F con 13. Scelgo G e visito i vicini, in questo caso solo G, ma 11+2 passando da G è uguale al peso 13 già individuato. Nno procedo ad alcun aggiornamento se non segnare lo step fatto.
| Nodi | B | C | D | E | F | G | |
| step 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | |
| step 1 | A | 5,A | 3,A | ∞ | ∞ | ∞ | ∞ |
| step 2 | AC | 7,C | 4,C | ∞ | ∞ | ||
| step 3 | ACE | 11,E | |||||
| step 4 | ACEB | # | |||||
| step 5 | ACEBD | 13,D | |||||
| step 6 | ACEBDG | # |
Step 7: resta solo un nodo non gestito, lo F. Qui non c’è molto da verificare poiché tutti i nodi adiacenti sono già stati elaborati dai precedenti step.
| Nodi | B | C | D | E | F | G | |
| step 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | |
| step 1 | A | 5,A | 3,A | ∞ | ∞ | ∞ | ∞ |
| step 2 | AC | 7,C | 4,C | ∞ | ∞ | ||
| step 3 | ACE | ∞ | 11,E | ||||
| step 4 | ACEB | # | ∞ | ||||
| step 5 | ACEBD | 13,D | |||||
| step 6 | ACEBDG | # | |||||
| step 7 | ACEBDGF |
Visitati tutti i nodi ed aggiornati i rispettivi pesi possiamo finalmente tracciare il percorso migliore A,C,E,G con peso totale 11
Ultima modifica 4 Settembre 2023
