Algoritmi/I cammini minimi

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:

1. 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;
2. 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

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