Algoritmi/I cammini minimi

Indice del libro

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 è . Più cammini possono essere tutti di peso minimo, ma il peso minimo è univoco.

Applicazioni modifica

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 modifica

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:[1]
    • 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 modifica

  • 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 modifica

Fondamenti teorici modifica

Posti due vertici vi e vj 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 vi a vj è esprimibile attraverso il sottocammino minimo da vi a vj − 1 + l'arco da vj − 1 a vj (non si trattano multigrafi → non si hanno più archi tra due stessi vertici).

Procedimento modifica

Usando un vettore dei pesi wt, inizialmente la radice s dista 0 da se stessa, e tutti i vertici distano  . 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 modifica

A ogni passo si considerano in maniera greedy i vertici non ancora stimati (= cioè appartenenti a VS) 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à
 

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 modifica

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

Note modifica

  1. In realtà non ha neanche senso parlare di ricerca di cammini minimi perché percorrendo il ciclo si arriva a una stima  .