# Algoritmi/I cammini minimi

Algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaAlgoritmi/Copertina
* Gli algoritmiAlgoritmi/Gli algoritmi
* L'analisi di complessità degli algoritmiAlgoritmi/L'analisi di complessità degli algoritmi
* Gli algoritmi di ordinamentoAlgoritmi/Gli algoritmi di ordinamento
* Grafi e alberiAlgoritmi/Grafi e alberi
* La ricorsioneAlgoritmi/La ricorsione
* Il paradigma "divide et impera"Algoritmi/Il paradigma "divide et impera"
* Gli heapAlgoritmi/Gli heap
* Le tabelle di simboliAlgoritmi/Le tabelle di simboli
* Alberi binari di ricerca (BST)Algoritmi/Alberi binari di ricerca (BST)
* Tipologie di problemiAlgoritmi/Tipologie di problemi
* Le tabelle di hashAlgoritmi/Le tabelle di hash
* L'ADT grafo non orientatoAlgoritmi/L'ADT grafo non orientato
* Gli algoritmi di visita dei grafiAlgoritmi/Gli algoritmi di visita dei grafi
* Le applicazioni degli algoritmi di visita dei grafiAlgoritmi/Le applicazioni degli algoritmi di visita dei grafi
* Gli alberi ricoprenti minimiAlgoritmi/Gli alberi ricoprenti minimi
* I cammini minimiAlgoritmi/I cammini minimi
Modifica il sommario
Si considerano grafi orientati e pesati. Il peso w di un cammino è la sommatoria dei pesi associati agli archi che compongono il cammino. Il peso minimo δ di un cammino tra u e v è uguale al minimo peso di tutti i cammini tra u e v se almeno uno esiste, altrimenti il peso è $+\infty$. Più cammini possono essere tutti di peso minimo, ma il peso minimo è univoco.

## Applicazioni

Si applica per esempio a reti di città con pesi corrispondenti alle distanze.

### Casi

* da sorgente singola: a partire da una città si calcolano i cammini minimi verso tutte le altre destinazioni;
* con destinazione singola: viceversa → basta risolvere con lo stesso algoritmo lavorando sul grafo trasposto;
* tra tutte le coppie di vertici: si calcolano i cammini minimi tra tutte le coppie di vertici (matrice triangolare) → basta iterare per tutti i vertici l'algoritmo con una sorgente singola.

## Grafi con archi a peso negativo

Si distinguono due casi:
* nessun arco (di peso negativo) appartiene a un ciclo con somma dei pesi negativa:
** algoritmo di Dijkstra: non garantisce la soluzione ottima (algoritmo greedy);
** algoritmo di Bellman-Ford: garantisce comunque la soluzione ottima;
* esiste almeno un arco (di peso negativo) appartenente a un ciclo con somma dei pesi negativa:
** algoritmo di Dijkstra: il risultato non ha senso perché non ha senso il problema, e non rileva neanche il ciclo a peso negativo;
** algoritmo di Bellman-Ford: è in grado di rilevare il ciclo a peso negativo.

## Rappresentazione

* vettore dei predecessori: per il nodo i-esimo riporta l'indice del padre se esiste, altrimenti −1;
* sottografo dei predecessori G$_π$ = (V$_π$, E$_π$): V$_π$ contiene tutti i vertici per cui esiste il padre + il vertice di partenza, E$_π$ contiene gli archi che connettono tutte le coppie di vertici padre-figlio di V$_π$ tranne il vertice di partenza;
* albero dei cammini minimi G' = (V', E'): V' contiene tutti i vertici raggiungibili dalla radice s dell'albero → siccome è un albero, esiste un solo cammino semplice che connette ogni vertice con la radice:
** se il grafo non è pesato (o di pesi unitari), basta fare una visita in ampiezza;
** se il grafo è pesato, durante la visita del grafo si utilizza una coda a priorità per rappresentare i pesi.

## Relaxation
### Fondamenti teorici

Posti due vertici v$_i$ e v$_j$ connessi da uno o più cammini per cui esiste un cammino minimo, si può prendere un qualsiasi sottocammino di quel cammino minimo. Se quel sottocammino non fosse ottimo, esisterebbe un altro sottocammino ottimo che abbasserebbe la stima del cammino complessivo → non è possibile → ogni sottocammino di un cammino minimo è minimo.
Un cammino ottimo da v$_i$ a v$_j$ è esprimibile attraverso il sottocammino minimo da v$_i$ a v$_{j−1}$ + l'arco da v$_{j−1}$ a v$_j$ (non si trattano multigrafi → non si hanno più archi tra due stessi vertici).

### Procedimento

Usando un vettore dei pesi wt, inizialmente la radice s dista 0 da se stessa, e tutti i vertici distano $+\infty$. A ogni passo si effettua la relaxation: si confronta con la stima precedente il peso del sottocammino minimo fino a j − 1 + il peso dell'arco → se la stima è migliore si prende la nuova distanza minima stimata, fino a quando non si raggiunge la distanza minima definitiva, poiché una relaxation effettuata su un cammino già minimo non ha più effetto.
L'algoritmo di Dijkstra applica una sola relaxation per ogni arco, e usa la coda a priorità; l'algoritmo di Bellman-Ford applica tante relaxation per arco quanti sono i vertici, e prima deve ordinare tutti i vertici.

## Algoritmo di Dijkstra

A ogni passo si considerano in maniera greedy i vertici non ancora stimati (= cioè appartenenti a V − S) raggiungibili dal vertice corrente, su cui poter applicare la relaxation. Usa una coda a priorità, dove la priorità corrisponde alla distanza minima correntemente stimata, in cui ogni vertice viene estratto una sola volta e non ristimando mai più di una volta una stima. Condizione di terminazione: la coda a priorità è vuota.

### Complessità

    $T\left(n\right)=O\left(\left(\left|V\right|+\left|E\right|\right)\log {\left|V\right|}\right)$
Se esiste un arco negativo, esso consentirebbe di ristimare la stima su un vertice già precedentemente stimato, ma quel vertice non entrerà mai più nella coda a priorità.

## Algoritmo di Bellman-Ford

* si ordinano gli archi attraverso un criterio di ordinamento stabilito;
* per ogni vertice si applicano $\left|V\right|-1$ relaxation;
* alla fine si verifica che per tutte le $\left|V\right|$-esime relaxation non migliorino alcuna stima, perché altrimenti esiste almeno un ciclo negativo.

## Note

* ↑ In realtà non ha neanche senso parlare di ricerca di cammini minimi perché percorrendo il ciclo si arriva a una stima $-\infty$.