Studio comparativo tra gli algoritmi di Dijkstra e Bellman-Ford

www.democraziadigitale.eu

Studio comparativo tra gli algoritmi di Dijkstra e Bellman-Ford

ANNO ACCADEMICO 2014/2015

Francesco Ciclosi

Camerino, febbraio 2015


© Francesco Ciclosi – febbraio 2015 – Tutti i diritti riservati.


Il problema dei cammini minimi

un problema di cammino minimo prevede

l’individuazione della via più breve per andare da un

punto di partenza (p), a un punto di arrivo (a)

Nella teoria dei grafi, il cammino minimo indica il

percorso che collega due vertici dati, minimizzando

la somma dei costi associati all’attraversamento di

ogni arco




Un problema molte varianti

cammini minimi a sorgente singola, per la

determinazione dei cammini minimi a partire da un

nodo prefissato;

cammini minimi tra tutte le coppie, per la

determinazione dei cammini minimi tra ogni nodo.

La maggior parte dei problemi è riconducibile al 1°




Archi con cicli di pesi negativi

Dati due vertici s e v, v è raggiungibile da s se

esiste almeno un cammino da s a v

La raggiungibilità

non è sufficiente a

garantire l’esistenza

di un cammino

minimo tra due

nodi




Il sottografo dei predecessori

Sia 𝐺 = (𝑉, 𝐸) un grafo orientato e pesato senza

cicli di peso negativo raggiungibili da 𝑠 ∈ 𝑉;

Il sottografo dei predecessori 𝐺𝜋 = 𝑉𝜋, 𝐸𝜋 è:

• 𝑉𝜋 = 𝑣 ∈ 𝑉: 𝜋 𝑣 ≠ 𝑁𝐼𝐿 ∪ 𝑠 , ovvero l’insieme

dei vertici 𝑉𝜋 è l’insieme composto dai vertici di 𝐺

aventi predecessore diverso da NIL, più la sorgente 𝑠

• 𝐸𝜋 = 𝜋 𝑣 , 𝑣 ∈ 𝐸: 𝑣 ∈ 𝑉𝜋 − 𝑠 , ovvero l’insieme

degli archi orientati 𝐸𝜋 è l’insieme di archi indotto dai

valori di 𝜋 per i vertici in 𝑉𝜋.




La tecnica del rilassamento

per ogni nodo 𝑢 del grafo, si memorizza un

attributo 𝑑 𝑢 (stima del cammino minimo)

𝑑 𝑢 è un limite superiore al peso di un cammino

minimo dalla sorgente 𝑠 a un nodo 𝑣 ∈ 𝑉

rilassare un arco (𝑢, 𝑣) vuol dire

• verificare se passando per 𝑢, si può migliorare il

cammino minimo per 𝑣 attualmente noto

• aggiornare conseguentemente i valori di 𝑑[𝑣] e 𝜋[𝑣]




Rappresentazione dell’output

L’output del problema dei cammini minimi a

sorgente singola è l’albero dei cammini minimi

La rappresentazione utilizza un array 𝜋, di

dimensione pari al numero dei nodi e tale che 𝜋 𝑢

contenga:

• il nodo padre di u

• -1 se u è la radice dell’albero (ovvero il nodo sorgente)




L’algoritmo di Dijkstra

Risolve il problema di cammini minimi con

sorgente singola

• su di un grafo orientato e pesato 𝐺 = (𝑉, 𝐸)

• nel caso in cui tutti gli archi hanno peso non negativo,

quindi 𝑤(𝑢, 𝑣) ≥ 0 per ogni arco (𝑢, 𝑣) ∈ 𝐸




Funzionamento – elementi utilizzati

• un insieme 𝑆 con i vertici aventi il peso di cammino

minimo dalla sorgente 𝑠 già determinato;

• una coda a priorità 𝑄 con i vertici aventi il peso di

cammino minimo dalla sorgente 𝑠 non già determinato;

• un array 𝑑 per memorizzare di volta in volta il peso del

cammino migliore temporaneo per ciascun nodo;

• un array 𝜋 in cui viene memorizzato l’albero dei

cammini




Algoritmo di Dijkstra: pseudocodice (1)

Utilizza le due seguenti procedure:




Algoritmo di Dijkstra: pseudocodice (2)




L’algoritmo di Bellman-Ford

Risolve il problema di cammini minimi con

sorgente singola

• su di un grafo orientato e pesato 𝐺 = (𝑉, 𝐸)

• anche nel caso più generale in cui i pesi degli archi

possono essere negativi

• identifica l’eventuale esistenza nel grafo di cicli di peso

negativo, che siano raggiungibili dalla sorgente

• produce l’albero dei cammini minimi con i relativi pesi,

se nel grafo non esistono i cicli di cui sopra




Algoritmo di Bellman-Ford: pseudocodice




Analisi comparativa

Analisi dell’algoritmo di Dijkstra

• descrizione, analisi asintotica, analisi della struttura

dati implementata per la coda di priorità

Analisi dell’algoritmo di Bellman-Ford

• descrizione, analisi asintotica

Comparazione riassuntiva tra i due algoritmi




Dijkstra: analisi (1)

L’efficienza dell’algoritmo dipende dalla struttura

dati usata per implementare la coda di priorità Q

La scelta dell’implementazione di Q non cambia

il comportamento dell’algoritmo

La scelta dell’implementazione di Q cambia la

complessità e l’efficienza dell’algoritmo




Dijkstra: analisi (2)

L’algoritmo si basa su tre operazioni principali

che sono la base per l’analisi della complessità

asintotica

• Inserimento (istruzione Q ← V)

• Estrazione del minimo (funzione Extract_Min())

• Decremento di una chiave (implicito nella funzione

Relax(u,v,w))




Coda di priorità su lista non ordinata

È la più semplice implementazione della coda

È realizzabile con un vettore di puntatori

Il tempo totale di esecuzione dell’algoritmo è

quindi Ο 𝐸 + 𝑉2 = Ο(𝑉2)

× |V| operazioni

× |E| operazioni




Coda di priorità su heap binario (1)

Realizza Q organizzando gli elementi in un

albero binario secondo la struttura min-heap

Mantiene 3 proprietà:

• Ogni elemento della coda corrisponde a un nodo

dell’albero binario

• Ogni nodo dell’albero binario diverso dalla radice ha

priorità ≥ a quella del nodo padre

• L’albero è completo fino al penultimo livello (h-1)




Coda di priorità su heap binario (2)

Dato un albero di n nodi, dalle tre proprietà

derivano le seguenti:

1. L’heap conterrà esattamente n nodi

2. Tutti i nodi dell’albero avranno priorità ≥ a

quella della radice

3. L’altezza è proporzionale a 𝑙𝑜𝑔2𝑛 che diviene un

limite superiore per ogni operazione sull’albero




Coda su heap binario: analisi asintotica

Il tempo totale di esecuzione dell’algoritmo è pari a

Ο 𝐸𝑙𝑜𝑔𝑉 + 𝑉𝑙𝑜𝑔𝑉 = Ο( 𝐸 + 𝑉 𝑙𝑜𝑔𝑉)

× |V| operazioni

× |E| operazioni




Coda di priorità su heap di Fibonacci

È la più efficiente coda con priorità utilizzabile

per l’algoritmo di Dijkstra

Ha le stesse prestazioni teoriche di un heap

tradizionale ma…

…permette inserimento e decremento di una

chiave in un tempo constante e non logaritmico

Fa uso dell’analisi in tempo ammortizzato




Struttura dati heap di Fibonacci (1)

Sono composti da una lista di alberi che soddisfano

l’ordinamento parziale min-heap (≤)




Struttura dati heap di Fibonacci (2)

Ogni nodo 𝑥 ha un puntatore 𝑝 𝑥 al padre e un puntatore 𝑐ℎ𝑖𝑙𝑑 𝑥

a uno dei suoi figli.

I figli di 𝑥 sono collegati da una lista circolare a doppio collegamento

Ogni figlio 𝑦 ha dei puntatori 𝑙𝑒𝑓𝑡 𝑦 e 𝑟𝑖𝑔ℎ𝑡 𝑦




L’analisi ammortizzata

Il tempo di esecuzione di una sequenza di

operazioni di una struttura dati è la media dei

tempi di esecuzione della sequenza

Sia n la dimensione di una struttura dati e k una

catena di operazioni su di essa

=> La complessità in tempo è la somma dei

tempi di caso pessimo divisa per k

=> Ottengo l’efficienza media nel caso pessimo




Il metodo del potenziale

È una tecnica usata nell’analisi ammortizzata

Si associa alla struttura dati D un potenziale 𝜙(𝐷),

definito in modo tale che:

• le operazioni meno costose lo incrementano

• le operazioni più costose lo diminuiscono

Il costo ammortizzato è quindi dato dalla somma

algebrica di costo effettivo e variazione di potenziale




Funzione potenziale per l’heap di Fibonacci Sia H un heap di Fibonacci

• 𝑡(𝐻) il numero di alberi nella lista delle radici di 𝐻

• 𝑚(𝐻) il numero dei nodi marcati in 𝐻

La funzione potenziale è così definita:

𝜙 𝐻 = 𝑡 𝐻 + 2𝑚 𝐻

• Assumiamo che un’applicazione che fa uso di un heap

di Fibonacci inizi con un heap vuoto

• => Il potenziale iniziale è dunque pari a 0 e rimarrà

positivo anche successivamente.




Coda su heap di Fibonacci: analisi asintotica

Il tempo totale di esecuzione dell’algoritmo è pari a

Ο(𝑉𝑙𝑜𝑔𝑉 + 𝐸)

× |V| operazioni

× |E| operazioni




Altre possibili implementazioni di Dijkstra




Bellman-Ford: analisi

L’algoritmo si basa su tre operazioni principali

basilari per l’analisi della complessità asintotica:

• Inizializzazione (funzione Initialize_Single_Source()) –

riga 1

• Rilassamento (funzione Relax(u,v,w))) – ciclo for delle

righe 2-4

• Diminuzione della stima del peso di cammino minimo

– ciclo for delle righe 5-7




Coda su heap di Fibonacci: analisi asintotica

Il tempo totale di esecuzione dell’algoritmo è Ο(𝑉𝐸)




Conclusioni (1)

Caso grafo con archi aventi pesi negativi

• Non supportato da Dijkstra

• Supportato da Bellman-Ford (rileva anche la presenza

di cicli negativi)

Tipologia:

• Dijkstra esempio di algoritmo Greedy

• Bellman-Ford esempio di programmazione dinamica




Conclusioni (2)

Rilassamento

• Entrambi utilizzano tale tecnica

• Dijkstra rilassa ogni arco una sola volta

• Bellman-Ford rilassa ogni arco del grafo |V|-1 volte

Complessità (caso migliore):

• Dijkstra Ο(𝑉𝑙𝑜𝑔𝑉 + 𝐸) con heap di Fibonacci

• Bellman-Ford Ο(VE) – risulta meno efficiente




Conclusioni (3)

La complessità di Dijkstra è strettamente connessa

alla complessità della sua coda di priorità

Θ(𝑉 + 𝑉 × 𝑇𝐸𝑥𝑡𝑟𝑎𝑐𝑡_𝑀𝑖𝑛() + 𝐸 × 𝑇𝑅𝑒𝑙𝑎𝑥 𝑢,𝑣,𝑤 )




I miei contatti linkedin

http://it.linkedin.com/pub/francesco-ciclosi/62/680/a06/

facebook

https://www.facebook.com/francesco.ciclosi

twitter

@francyciclosi

www

http://www.francescociclosi.it

Studio comparativo tra gli algoritmi di Dijkstra e Bellman-Ford

Presentations & Public Speaking

Transcript of Studio comparativo tra gli algoritmi di Dijkstra e Bellman-Ford