Il problema di trovare il cammino minimo all’interno di un grafo è un concetto fondamentale nella teoria dei grafi e ha applicazioni pratiche sterminate in diversi settori. Che si tratti di determinare il percorso più breve per un navigatore GPS, di ottimizzare la logistica delle consegne, di instradare pacchetti di dati in una rete di computer, o di pianificare percorsi efficienti nei trasporti pubblici, la capacità di identificare il cammino meno “costoso” (in termini di tempo, distanza, denaro o altre metriche) è cruciale.

Questo articolo esplorerà due approcci principali per risolvere il problema del cammino minimo in un grafo orientato con costi non negativi: l’algoritmo di Dijkstra e la formulazione tramite Programmazione Lineare (PL). L’algoritmo di Dijkstra è una soluzione algoritmica diretta, nota per la sua efficienza e la sua natura “greedy”, che lo rende ideale per scenari con costi positivi. La Programmazione Lineare, d’altra parte, offre un potente framework matematico per modellare e risolvere problemi di ottimizzazione, fornendo una prospettiva complementare e generalizzabile.

Attraverso un esempio pratico, vedremo come applicare passo dopo passo l’algoritmo di Dijkstra per trovare il cammino minimo da un nodo sorgente a un nodo destinazione. Successivamente, formuleremo lo stesso problema come un modello di Programmazione Lineare, dimostrando come entrambe le metodologie convergano alla stessa soluzione ottima. Questo confronto evidenzierà non solo la validità di entrambi gli approcci, ma anche le rispettive forze e contesti di applicazione.

Esercizio

Si consideri il seguente grafo orientato [math]G = (V, E)[/math], in cui per ciascun arco [math](i,j) \in E[/math] è riportato il costo [math]c_{ij}[/math]:

1. Applicare l’algoritmo di Dijkstra per determinare un cammino minimo dal nodo al nodo

2. Formulare il problema come problema di programmazione lineare e determinarne una soluzione ottima

Soluzione

Spiegazione del Grafo nel Contesto dell’Esercizio

Il grafo visualizzato nell’immagine è un grafo orientato, denotato come $G = (V, E)$ , dove $V$ è l’insieme dei nodi e $E$ è l’insieme degli archi. Ogni arco $(i, j) \in E$ ha una direzione specifica (dal nodo $i$ al nodo $j$ , indicata da una freccia) e un costo $c_{ij}$ associato. L’obiettivo principale dell’esercizio è trovare il cammino minimo dal nodo sorgente s al nodo destinazione 6.

Componenti del Grafo e loro Rilevanza:

Nodi (Vertici, $V$ ):
- I nodi sono gli elementi fondamentali del grafo e rappresentano i “punti” o “stati” attraverso cui possiamo muoverci. Nel nostro grafo, i nodi sono s, 1, 2, 3, 4, 5, 6, 7.
- Nodo Sorgente (s): È il punto di partenza del nostro cammino. Tutte le ricerche di cammino minimo inizieranno da qui.
- Nodo Destinazione (6): È il punto d’arrivo desiderato per il cammino minimo. L’algoritmo di Dijkstra e la formulazione di Programmazione Lineare saranno finalizzati a raggiungere questo specifico nodo.
- Gli altri nodi (1, 2, 3, 4, 5, 7) sono nodi intermedi che possono far parte del cammino o servire da punti di transito.
Archi (Lati, $E$ ):
- Gli archi rappresentano le connessioni dirette tra i nodi e la possibilità di spostamento. Essendo un grafo orientato, un arco da $i$ a $j$ non implica un arco da $j$ a $i$ (a meno che non sia esplicitamente disegnato).
- Ogni arco è un “segmento” del cammino potenziale. Ad esempio, esiste un arco da s a 1, ma non esiste un arco diretto da 1 a s.
Costi degli Archi ( $c_{ij}$ ):
- Ogni arco $(i, j)$ ha un valore numerico positivo accanto ad esso. Questo valore $c_{ij}$ rappresenta il “costo” per attraversare quell’arco. Questo costo può essere interpretato come distanza, tempo, spesa, o qualsiasi altra metrica che vogliamo minimizzare.
- Esempi di costi:
  - $c_{s, 1} = 7$
  - $c_{1, 2} = 1$
  - $c_{1, 4} = 5$
  - $c_{4, 3} = 4$
  - $c_{3, 6} = 3$
  - $c_{6, 7} = 2$
  - $c_{7, 5} = 1$
- Rilevanza per l’Esercizio:
  - Tutti i costi degli archi sono non negativi: Questa è una condizione fondamentale per l’applicazione dell’Algoritmo di Dijkstra. Se ci fossero stati archi con costi negativi (e cicli negativi), Dijkstra non sarebbe applicabile direttamente e si dovrebbe ricorrere ad algoritmi diversi (come Bellman-Ford) o a formulazioni di PL più complesse.
  - L’obiettivo di entrambi i metodi (Dijkstra e PL) sarà sommare i costi degli archi inclusi nel cammino per trovare la sequenza di archi che porta dal nodo s al nodo 6 con la somma totale minima.

Forse potrebbe interessarti anche: Algoritmo di Dijkstra: Trovare il Cammino Più Breve con Esempio Python per Data Scientist e Sviluppatori

Nell’esercizio:

Algoritmo di Dijkstra: Sarà applicato iterativamente, “esplorando” il grafo a partire da s e calcolando progressivamente il cammino minimo a ogni nodo incontrato, finché il nodo 6 non viene “visitato” e il suo costo minimo definitivo è determinato.
Programmazione Lineare: Il grafo fornirà la base per definire le variabili di decisione (se un arco è utilizzato o meno), la funzione obiettivo (la somma dei costi degli archi utilizzati) e i vincoli di flusso (assicurando che ci sia un “flusso unitario” da s a 6 attraverso il cammino). La struttura degli archi e i loro costi saranno direttamente inseriti nel modello matematico.

In sintesi, il grafo è la rappresentazione visiva e strutturale del problema di ottimizzazione. I nodi e gli archi con i loro costi definiscono tutte le possibili “rotte” e i relativi “oneri”, e l’esercizio richiede di navigare questa struttura per identificare la rotta più efficiente dal punto di vista del costo.

1. Algoritmo di Dijkstra – Cammino minimo da [math]s[/math] a [math]6[/math]

Applichiamo l’algoritmo di Dijkstra, che serve per trovare il cammino minimo in un grafo orientato con pesi non negativi.

👉Cammini Minimi: Algoritmo Dijkstra e Programmazione Lineare (Esercizio Svolto con Grafo Orientato)

Inizializzazione:

[math]\rho(v) = +\infty[/math] per ogni nodo [math]v \neq s[/math]
[math]\rho(s) = 0[/math]
Insieme dei nodi con etichetta permanente: [math]W = \emptyset[/math]

Procediamo con l’algoritmo fino a quando il nodo 6 ottiene etichetta permanente (criterio di stopping).

Step-by-step – Tabelle dei valori [math]\rho[/math] e predecessori:

[math]W[/math]	[math]\rho(1)[/math]	[math]\rho(2)[/math]	[math]\rho(3)[/math]	[math]\rho(4)[/math]	[math]\rho(5)[/math]	[math]\rho(6)[/math]	[math]\rho(7)[/math]
[math]\emptyset[/math]	[math]+\infty[/math]	[math]+\infty[/math]	[math]+\infty[/math]	[math]+\infty[/math]	[math]+\infty[/math]	[math]+\infty[/math]	[math]+\infty[/math]
[math]\{s\}[/math]	1	[math]+\infty[/math]	[math]+\infty[/math]	[math]+\infty[/math]	[math]+\infty[/math]	[math]+\infty[/math]	[math]+\infty[/math]
[math]\{s,1\}[/math]	1	3	5	2	[math]+\infty[/math]	[math]+\infty[/math]	[math]+\infty[/math]
[math]\{s,1,4\}[/math]	1	3	3	2	[math]+\infty[/math]	[math]+\infty[/math]	[math]+\infty[/math]
[math]\{s,1,4,2\}[/math]	1	3	3	2	[math]+\infty[/math]	[math]+\infty[/math]	[math]+\infty[/math]
[math]\{s,1,4,2,3\}[/math]	1	3	3	2	9	4	[math]+\infty[/math]
[math]\{s,1,4,2,3,6\}[/math]	1	3	3	2	9	4	[math]+\infty[/math]

Forse potrebbe interessarti anche: Algoritmo di Dijkstra e Supply Chain: 2 esercizi introduttivi tra grafi, Python e logistica

Nodo	[math]pred(s)[/math]	[math]pred(1)[/math]	[math]pred(2)[/math]	[math]pred(3)[/math]	[math]pred(4)[/math]	[math]pred(5)[/math]	[math]pred(6)[/math]	[math]pred(7)[/math]
Predecessore	s	s	1	4	1	s	3	s

Ricostruzione del cammino minimo [math]s \to 6[/math]

Dalla tabella dei predecessori:

[math]pred(6) = 3[/math]
[math]pred(3) = 4[/math]
[math]pred(4) = 1[/math]
[math]pred(1) = s[/math]

Quindi il cammino minimo è:

[math]s \to 1 \to 4 \to 3 \to 6[/math]

Costo totale: [math]c(s,1) + c(1,4) + c(4,3) + c(3,6) = 1 + 1 + 1 + 1 = \boxed{4}[/math]

2. Formulazione come problema di Programmazione Lineare

Variabili decisionali:

Per ogni arco [math](i,j) \in E[/math], definiamo una variabile binaria:

[math]
\displaystyle
x_{ij} =
\begin{cases}
1 & \text{se l’arco } (i,j) \text{ è incluso nel cammino} \\
0 & \text{altrimenti}
\end{cases}
[/math]

Funzione obiettivo:

Minimizzare il costo totale del cammino:

[math]
\min \sum_{(i,j)\in E} c_{ij} x_{ij}
[/math]

Vincoli di flusso (modello di cammino minimo):

Per ogni nodo [math]v \in V[/math], definiamo:

[math]
\displaystyle
\sum_{j : (v,j) \in E} x_{vj} – \sum_{i : (i,v) \in E} x_{iv} =
\begin{cases}
1 & \text{se } v = s \\
-1 & \text{se } v = 6 \\
0 & \text{altrimenti}
\end{cases}
[/math]

Vincoli di non negatività e binarietà:

[math]x_{ij} \in \{0,1\} \quad \forall (i,j) \in E[/math]

Soluzione ottima (valori delle variabili [math]x_{ij}[/math])

Sulla base del cammino minimo trovato:

[math]
\displaystyle
\begin{aligned}
x_{s1} &= 1 \\
x_{14} &= 1 \\
x_{43} &= 1 \\
x_{36} &= 1 \\
\text{tutti gli altri } x_{ij} &= 0
\end{aligned}
[/math]

Costo totale:

[math]c(s,1) + c(1,4) + c(4,3) + c(3,6) = 1 + 1 + 1 + 1 = \boxed{4}[/math]

✅ Conclusione

Abbiamo risolto il problema sia tramite l’algoritmo di Dijkstra sia tramite una formulazione di programmazione lineare. In entrambi i casi, il cammino minimo da [math]s[/math] a [math]6[/math] è:

[math]\boxed{s \to 1 \to 4 \to 3 \to 6} \quad \text{con costo totale } \boxed{4}[/math]

Commento Teorico ed Applicativo

Algoritmo di Dijkstra

L’algoritmo di Dijkstra è un pilastro della teoria dei grafi, noto per la sua efficienza e la sua vasta applicabilità. Si distingue per la sua natura “greedy”, in cui ad ogni passo si seleziona il nodo non visitato con il costo cumulativo minore dalla sorgente. Questa strategia funziona perfettamente per grafi con pesi non negativi perché, una volta che un nodo riceve un’etichetta permanente, significa che il cammino trovato per esso è il cammino minimo assoluto, e nessun altro percorso futuro potrà migliorarlo.

Forse potrebbe interessarti anche: Scopri il Modello di Hotelling e la Strategia della Differenziazione Spaziale

Applicazioni pratiche di Dijkstra sono ubiquitarie: dalla determinazione dei percorsi più brevi in sistemi di navigazione GPS, alla pianificazione di reti di telecomunicazioni, fino alla gestione del traffico di rete e all’ottimizzazione logistica. La sua semplicità concettuale lo rende un ottimo punto di partenza per comprendere algoritmi più complessi di ricerca di cammini.

Programmazione Lineare per il Cammino Minimo

Formulare il problema del cammino minimo come un problema di Programmazione Lineare (PL) offre una prospettiva diversa e complementare all’approccio algoritmico diretto. La PL è una potente metodologia matematica per ottimizzare una funzione obiettivo lineare soggetta a vincoli lineari. Nel contesto del cammino minimo, la formulazione come PL di flusso su rete (o, più specificamente, come problema di flusso unitario da sorgente a destinazione) è una rappresentazione elegante e formalmente rigorosa.

Questa formulazione è particolarmente utile per diverse ragioni:

Generalizzabilità: la PL consente di aggiungere facilmente altri vincoli o di modificare la funzione obiettivo per adattarsi a scenari più complessi (es. capacità degli archi, più sorgenti/destinazioni, ecc.), trasformando il problema in un problema di flusso di costo minimo più generale.
Robustezza: sebbene Dijkstra sia più efficiente per il problema specifico del cammino minimo con costi non negativi, la PL può gestire anche grafi con costi negativi (sebbene senza cicli negativi) tramite algoritmi specifici per la PL (es. il Simplex).
Strumenti Software: esistono potenti risolutori (solver) di PL (es. Gurobi, CPLEX, GLPK) in grado di risolvere problemi di grandi dimensioni, rendendo questa formulazione pratica per applicazioni su larga scala.

La corrispondenza tra la soluzione della PL e quella di Dijkstra in questo caso sottolinea come la PL possa catturare l’essenza di un problema algoritmico in un formalismo matematico, fornendo una base per l’analisi teorica e la generalizzazione. Questo approccio è fondamentale in campi come la Ricerca Operativa e l’Ottimizzazione.