Il cammino minimo è il problema di trovare, in un grafo pesato, il percorso di costo minimo tra una sorgente e una destinazione oppure tra una sorgente e tutti gli altri nodi. Il grafo può rappresentare una rete stradale, una rete logistica, una rete di telecomunicazioni, un grafo di stati o un modello astratto di decisioni.
Dato un nodo sorgente s, una forma della ricorrenza di ottimalità è:
d_j è la distanza minima dal nodo sorgente al nodo j, c_{ij} è il costo dell’arco (i,j) e A è l’insieme degli archi. L’idea algoritmica centrale è il rilassamento: se passare da i a j migliora la distanza nota di j, allora si aggiorna l’etichetta di j.
La scelta dell’algoritmo dipende dalle proprietà dei costi:
| Caso | Metodo tipico |
|---|---|
| costi non negativi | Dijkstra |
| costi anche negativi, senza cicli negativi | Bellman-Ford |
| grafo aciclico orientato | ordinamento topologico e rilassamenti |
| tutte le coppie di nodi | Floyd-Warshall o ripetizione di metodi a sorgente singola |
Se esiste un ciclo a costo negativo raggiungibile dalla sorgente, il problema di minimo non è ben definito: percorrere il ciclo ripetutamente abbassa il costo senza limite. In quel caso non ha senso chiedere il “cammino minimo” nel senso usuale, perché non esiste un valore ottimo finito.
Il problema può essere formulato anche come programma lineare su rete. Le variabili indicano se un arco appartiene al cammino, mentre i vincoli conservano il flusso nei nodi intermedi. Questa lettura collega il cammino minimo ad altri problemi di ottimizzazione su reti, come flusso massimo, trasporto e assegnamento.
Nelle applicazioni reali il costo non è sempre una distanza geometrica. Può essere tempo di percorrenza, rischio, consumo energetico, ritardo di rete, penalità economica o una funzione composta. Per questo la modellazione del peso degli archi è spesso più delicata dell’algoritmo stesso: un cammino ottimo rispetto ai chilometri può essere pessimo rispetto a tempi, affidabilità o vincoli operativi.
Vedi anche: Ottimizzazione su reti, Flusso massimo, Programmazione dinamica, Algoritmo.