Visualizza wikitesto di Algoritmi/I cammini minimi

{{Algoritmi}}
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 è <math>+ \infty</math>. 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:<ref>In realtà non ha neanche senso parlare di ricerca di cammini minimi perché percorrendo il ciclo si arriva a una stima <math>- \infty</math>.</ref>
#* 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==
* <span style="text-decoration:underline;">vettore dei predecessori:</span> per il nodo ''i''-esimo riporta l'indice del padre se esiste, altrimenti −1;
* <span style="text-decoration: underline">sottografo dei predecessori ''G''<sub>π</sub> = (''V''<sub>π</sub>, ''E''<sub>π</sub>):</span> ''V''<sub>π</sub> contiene tutti i vertici per cui esiste il padre + il vertice di partenza, ''E''<sub>π</sub> contiene gli archi che connettono tutte le coppie di vertici padre-figlio di ''V''<sub>π</sub> tranne il vertice di partenza;
* <span style="text-decoration: underline">albero dei cammini minimi ''G''<nowiki>'</nowiki> = (''V''<nowiki>'</nowiki>, ''E''<nowiki>'</nowiki>):</span> ''V''<nowiki>'</nowiki> 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<sub>i</sub>'' e ''v<sub>j</sub>'' 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<sub>i</sub>'' a ''v<sub>j</sub>'' è esprimibile attraverso il sottocammino minimo da ''v<sub>i</sub>'' a ''v''<sub>''j'' − 1</sub> + l'arco da ''v''<sub>''j'' − 1</sub> a ''v<sub>j</sub>'' (non si trattano multigrafi → non si hanno più archi tra due stessi vertici).

===Procedimento===
Usando un vettore dei pesi <code>wt</code>, inizialmente la radice ''s'' dista 0 da se stessa, e tutti i vertici distano <math>+ \infty</math>. 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à
:<math>T \left(n \right) = O \left( \left( \left| V \right| + \left| E \right| \right) \log{\left| V \right|} \right)</math>

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 <math>\left| V \right| -1</math> relaxation;
# alla fine si verifica che per tutte le <math>\left| V \right|</math>-esime relaxation non migliorino alcuna stima, perché altrimenti esiste almeno un ciclo negativo.

==Note==
<references />
[[Categoria:Algoritmi|{{SUBPAGENAME}}]]