Algoritmo di Dijkstra con esercizo svolto

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