FANDOM


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

ApplicazioniModifica

3 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 negativoModifica

Si distinguono due casi:

  1. 4 messun 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.

RappresentazioneModifica

  • 7 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;
  • 8 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.

RelaxationModifica

Fondamenti teoriciModifica

13 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.

14 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).

ProcedimentoModifica

16 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, 20 fino a quando non si raggiunge la distanza minima definitiva, poiché 21 una relaxation effettuata su un cammino già minimo non ha più effetto.

22 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 DijkstraModifica

23 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.

31 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-FordModifica

  1. 32 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.

NoteModifica

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

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Inoltre su FANDOM

Wiki casuale