Cammini Minimi in un Grafo Orientato

Il problema dei cammini minimi è uno dei problemi fondamentali e più studiati nell’ambito della teoria dei grafici e dell’ottimizzazione combinatoria, con applicazioni che spaziano dalla navigazione GPS alla pianificazione di reti logistiche, dal routing del traffico dati alla bioinformatica. In termini generali, consiste nel trovare, tra due nodi di un grafo (o da una sorgente a tutti gli altri nodi), un percorso la cui somma dei pesi (o costi) degli archi sia la minima possibile.

Questo esercizio si propone di affrontare il problema dei cammini minimi da una singola sorgente su un grafico orientato con pesi non negativi, esplorando due potenti approcci per la sua risoluzione: l’algoritmo classico di Dijkstra e una formulazione alternativa basata sulla programmazione lineare.

Attraverso lo svolgimento dettagliato su un grafico specifico, illustreremo passo dopo passo l’applicazione dell’algoritmo di Dijkstra per determinare le distanze minime e l’albero dei cammini minimi. Successivamente, mostreremo come lo stesso problema potrà essere modellato formalmente come un problema di programmazione lineare, definendo variabili, funzione obiettivo e vincoli pertinenti. L’analisi della soluzione ottima di tale formulazione ci permetterà di verificare l’equivalenza tra i risultati ottenuti dai due metodi, evidenziando la versatilità degli strumenti matematici e algoritmici nella soluzione di problemi complessi su reti.

Esercizio:

Sia dato un grafo orientato [math]G(V,E)[/math] caratterizzato da 8 nodi ([math]V=\{s,1,2,3,4,5,6,7\}[/math]) e 13 archi. A ciascun arco [math]e[/math] è associato un costo secondo le seguenti tabelle:

Arco	Costo	Arco	Costo
(s,1)	1	(3,6)	1
(s,2)	4	(4,3)	1
(1,2)	2	(6,4)	5
(1,3)	4	(6,5)	9
(1,4)	1	(6,7)	1
(2,4)	4	(7,5)	2
(3,5)	6

Si richiedono i seguenti punti:

1. Determinare l’albero dei cammini minimi dal nodo [math]s[/math] a tutti gli altri nodi, applicando l’algoritmo di Dijkstra;
2. Formulare il problema come problema di programmazione lineare e determinarne una soluzione ottima.

Svolgimento

👉Algoritmo di Dijkstra: Trovare il Cammino Più Breve con Esempio Python

Punto 1: Algoritmo di Dijkstra

Applichiamo l’algoritmo di Dijkstra con i costi forniti dalle tabelle.

Inizializzazione:

• [math]d[s]=0[/math], [math]p[s]=\text{NIL}[/math]
• [math]d[v]=\infty[/math], [math]p[v]=\text{NIL}[/math] per [math]v \in V \setminus \{s\}[/math]
• [math]Q=V[/math]

Iterazione 1:

Estraggo [math]s[/math] da [math]Q[/math]. [math]d[s]=0[/math].
Aggiorno i vicini di [math]s[/math]:

• Arco (s,1): [math]d[1]=\min(\infty,d[s]+\text{costo}(s,1))=\min(\infty,0+1)=1[/math]. [math]p[1]=s[/math].
• Arco (s,2): [math]d[2]=\min(\infty,d[s]+\text{costo}(s,2))=\min(\infty,0+4)=4[/math]. [math]p[2]=s[/math].

[math]Q=\{1,2,3,4,5,6,7\}[/math]
Distanze attuali: [math]d[s]=0, d[1]=1, d[2]=4, d[3]=\infty, d[4]=\infty, d[5]=\infty, d[6]=\infty, d[7]=\infty[/math].

Iterazione 2:

Estraggo il nodo con distanza minima da [math]Q[/math], che è 1 ([math]d[1]=1[/math]).
Aggiorno i vicini di 1:

• Arco (1,2): [math]d[2]=\min(4,d[1]+\text{costo}(1,2))=\min(4,1+2)=3[/math]. [math]p[2]=1[/math].
• Arco (1,3): [math]d[3]=\min(\infty,d[1]+\text{costo}(1,3))=\min(\infty,1+4)=5[/math]. [math]p[3]=1[/math].
• Arco (1,4): [math]d[4]=\min(\infty,d[1]+\text{costo}(1,4))=\min(\infty,1+1)=2[/math]. [math]p[4]=1[/math].

[math]Q=\{2,3,4,5,6,7\}[/math]
Distanze attuali: [math]d[s]=0, d[1]=1, d[2]=3, d[3]=5, d[4]=2, d[5]=\infty, d[6]=\infty, d[7]=\infty[/math].

Iterazione 3:

Estraggo il nodo con distanza minima da [math]Q[/math], che è 4 ([math]d[4]=2[/math]).
Aggiorno i vicini di 4:

• Arco (4,3): [math]d[3]=\min(5,d[4]+\text{costo}(4,3))=\min(5,2+1)=3[/math]. [math]p[3]=4[/math].

[math]Q=\{2,3,5,6,7\}[/math]
Distanze attuali: [math]d[s]=0, d[1]=1, d[2]=3, d[3]=3, d[4]=2, d[5]=\infty, d[6]=\infty, d[7]=\infty[/math].

Iterazione 4:

Estraggo un nodo con distanza minima da [math]Q[/math]. Possiamo scegliere 2 ([math]d[2]=3[/math]) o 3 ([math]d[3]=3[/math]). Scegliamo 2.
Aggiorno i vicini di 2:

• Arco (2,4): [math]d[4]=\min(2,d[2]+\text{costo}(2,4))=\min(2,3+4)=2[/math]. Nessun cambiamento.

[math]Q=\{3,5,6,7\}[/math]
Distanze attuali: [math]d[s]=0, d[1]=1, d[2]=3, d[3]=3, d[4]=2, d[5]=\infty, d[6]=\infty, d[7]=\infty[/math].

Iterazione 5:

Estraggo il nodo con distanza minima da [math]Q[/math], che è 3 ([math]d[3]=3[/math]).
Aggiorno i vicini di 3:

• Arco (3,5): [math]d[5]=\min(\infty,d[3]+\text{costo}(3,5))=\min(\infty,3+6)=9[/math]. [math]p[5]=3[/math].
• Arco (3,6): [math]d[6]=\min(\infty,d[3]+\text{costo}(3,6))=\min(\infty,3+1)=4[/math]. [math]p[6]=3[/math].

[math]Q=\{5,6,7\}[/math]
Distanze attuali: [math]d[s]=0, d[1]=1, d[2]=3, d[3]=3, d[4]=2, d[5]=9, d[6]=4, d[7]=\infty[/math].

Iterazione 6:

Estraggo il nodo con distanza minima da [math]Q[/math], che è 6 ([math]d[6]=4[/math]).
Aggiorno i vicini di 6:

• Arco (6,4): [math]d[4]=\min(2,d[6]+\text{costo}(6,4))=\min(2,4+5)=2[/math]. Nessun cambiamento.
• Arco (6,5): [math]d[5]=\min(9,d[6]+\text{costo}(6,5))=\min(9,4+9)=9[/math]. Nessun cambiamento.
• Arco (6,7): [math]d[7]=\min(\infty,d[6]+\text{costo}(6,7))=\min(\infty,4+1)=5[/math]. [math]p[7]=6[/math].

[math]Q=\{5,7\}[/math]
Distanze attuali: [math]d[s]=0, d[1]=1, d[2]=3, d[3]=3, d[4]=2, d[5]=9, d[6]=4, d[7]=5[/math].

Iterazione 7:

Estraggo il nodo con distanza minima da [math]Q[/math], che è 7 ([math]d[7]=5[/math]).
Aggiorno i vicini di 7:

• Arco (7,5): [math]d[5]=\min(9,d[7]+\text{costo}(7,5))=\min(9,5+2)=7[/math]. [math]p[5]=7[/math].

[math]Q=\{5\}[/math]
Distanze attuali: [math]d[s]=0, d[1]=1, d[2]=3, d[3]=3, d[4]=2, d[5]=7, d[6]=4, d[7]=5[/math].

Iterazione 8:

Estraggo il nodo con distanza minima da [math]Q[/math], che è 5 ([math]d[5]=7[/math]).
Aggiorno i vicini di 5: Nessun arco uscente da 5.

[math]Q=\emptyset[/math]. L’algoritmo termina.

Distanze Minime Finali :

• [math]d[s]=0[/math]
• [math]d[1]=1[/math]
• [math]d[2]=3[/math]
• [math]d[3]=3[/math]
• [math]d[4]=2[/math]
• [math]d[5]=7[/math]
• [math]d[6]=4[/math]
• [math]d[7]=5[/math]

Albero dei Cammini Minimi:

Gli archi che formano l’albero, basati sui predecessori finali, sono:

• (s,1)
• (1,2)
• (4,3)
• (1,4)
• (7,5)
• (3,6)
• (6,7)

Gli archi che formano l’albero sono: (s,1),(1,2),(4,3),(1,4),(7,5),(3,6),(6,7).

Punto 2: Formulazione come Problema di Programmazione Lineare

Definiamo le variabili di decisione:

• [math]d_v[/math]: la lunghezza del cammino minimo dal nodo sorgente [math]s[/math] al nodo [math]v[/math], per ogni [math]v \in V[/math].

Funzione Obiettivo:

Massimizzare [math]\sum_{v \in V \setminus \{s\}} d_v[/math]

Massimizzare [math]d_1+d_2+d_3+d_4+d_5+d_6+d_7[/math]

Vincoli:

[math]d_v \leq d_u + \text{costo}(u,v)[/math], per ogni [math](u,v) \in E[/math].
[math]d_s = 0[/math]
[math]d_v \geq 0[/math], per ogni [math]v \in V[/math].

Formulazione Completa del PL :

Massimizzare [math]d_1+d_2+d_3+d_4+d_5+d_6+d_7[/math]

Soggetto a:

• [math]d_1 \leq d_s + 1[/math]
• [math]d_2 \leq d_s + 4[/math]
• [math]d_2 \leq d_1 + 2[/math]
• [math]d_3 \leq d_1 + 4[/math]
• [math]d_4 \leq d_1 + 1[/math]
• [math]d_4 \leq d_2 + 4[/math]
• [math]d_5 \leq d_3 + 6[/math]
• [math]d_6 \leq d_3 + 1[/math]
• [math]d_3 \leq d_4 + 1[/math]
• [math]d_4 \leq d_6 + 5[/math]
• [math]d_5 \leq d_6 + 9[/math]
• [math]d_7 \leq d_6 + 1[/math]
• [math]d_5 \leq d_7 + 2[/math]
• [math]d_s = 0[/math]
• [math]d_v \geq 0[/math], per [math]v \in \{s,1,2,3,4,5,6,7\}[/math]

Questi vincoli [math]d_v \leq d_u + \text{costo}(u,v)[/math]  sono noti come disuguaglianze di Bellman-Ford e rappresentano una condizione necessaria affinché [math]d_v[/math] sia la distanza del cammino minimo dalla sorgente [math]s[/math] a [math]v[/math]. La formulazione LP cerca i valori di [math]d_v[/math] che soddisfano tutte queste disuguaglianze (e [math]d_s = 0[/math]) e massimizzano la somma, garantendo così che i [math]d_v[/math] assumere i valori delle distanze minime.

Soluzione Ottima :

La soluzione ottima di questo problema di programmazione lineare corrisponde alle distanze minime calcolate con l’algoritmo di Dijkstra.

Pertanto, la soluzione ottima è:

• [math]d_s = 0[/math]
• [math]d_1 = 1[/math]
• [math]d_2 = 3[/math]
• [math]d_3 = 3[/math]
• [math]d_4 = 2[/math]
• [math]d_5 = 7[/math]
• [math]d_6 = 4[/math]
• [math]d_7 = 5[/math]

Conclusione

Lo svolgimento di questo esercizio ha permesso di affrontare il problema fondamentale della determinazione dei cammini minimi da una singola sorgente in un grafico orientato con pesi non negativi, impiegando due approcci distinti ma profondamente correlati.

L’applicazione passo passo dell’algoritmo di Dijkstra ha illustrato il funzionamento di questo efficiente metodo greedy, che procedendo iterativamente e rilassando gli archi in base al nodo con distanza stimata minima, garantisce il ritrovamento delle distanze minime per tutti i nodi raggiungibili dalla sorgente. Le distanze finali calcolate e l’albero dei cammini minimi derivato dai predecessori rappresentano l’output diretto dell’algoritmo.

Parallelamente, abbiamo esplorato la possibilità di modellare il medesimo problema nel quadro della programmazione lineare. La formulazione presentata, basata sulle disuguaglianze di Bellman-Ford che caratterizzano le distanze minime, e l’obiettivo di massimizzare le distanze stimate, hanno dimostrato come la soluzione ottima di un problema di ottimizzazione matematica possa coincidere perfettamente con i risultati ottenuti da un algoritmo specifico sui grafici. Le distanze minime trovate con Dijkstra sono, come atteso, la soluzione ottima unica per le variabili [math]d_v[/math] in questo specifico problema di programmazione lineare.

Questa comparazione non solo valida i risultati, ma sottolinea anche l’interconnessione tra l’algoritmica e l’ottimizzazione matematica. Comprendere entrambi gli approcci arricchisce la capacità di analizzare e risolvere problemi complessi su reti, scegliendo lo strumento più appropriato a seconda del contesto o della necessità di integrare il problema dei cammini minimi all’interno di modelli decisionali più ampi.

Pubblicità