Capitolo 13 Cammini minimi: Algoritmo di Dijkstra; Algoritmo di Floyd e Warshall Algoritmi e...

Capitolo 13Cammini minimi:

Algoritmo di Dijkstra; Algoritmo di Floyd e Warshall

Algoritmi e Strutture Dati

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl2

Punto della situazione• Algoritmo di ordinamento topologico: albero dei cammini minimi

in grafi (diretti) aciclici. Complessità Θ(n+m) (con liste di adiacenza). Come si ottiene?

– Basta associare inizialmente ad ogni nodo il proprio grado entrante. Tale valore può essere calcolato in Θ(n+m) scorrendo le liste di adiacenza. Quindi, manteniamo una lista Z dei nodi con grado entrante pari a 0. Tale lista si può costruire in Θ(n), ovviamente. Quindi, selezioniamo un elemento di tale lista e lo eliminiamo dal grafo, assieme a tutti gli archi uscenti. Per ogni arco uscente eliminato, diminuiamo di 1 il grado entrante del nodo di arrivo corrispondente, ed aggiungiamo eventualmente il nodo a

Z se il suo grado entrante si è azzerato.

• Algoritmo di Bellman&Ford: albero dei cammini minimi per tutti i grafi che non contengono cicli negativi. Complessità Θ(n·m) (con liste di adiacenza).



Algoritmo di Dijkstra(albero dei cammini minimi

in grafi con pesi non negativi)



Estendere l’albero dei cammini minimi Lemma di Dijkstra (1959): Sia G=(V,E,w) diretto con pesi non negativi, e sia T un sottoalbero dell’albero dei cammini minimi radicato in s che include s ma non include tutti i vertici raggiungibili da s. Sia (u,v) l’arco che minimizza la quantità dst+ w(t,z), per ogni tT e zT. Allora, (u,v) appartiene a un cammino minimo da s a v.Dim.: Supponiamo per assurdo che (u,v) non appartenga ad un cammino minimo da s a v, e quindi che dsv< dsu+w(u,v). Allora, dsv è la lunghezza di un cammino minimo da s a v che non passa per (u,v). Tale cammino, per uscire da T, deve allora passare per un qualche arco (x,y)(u,v), con xT e yT. Sia quindi sv = <s,…,x,y,…,v>.



Per la minimalità dei sottocammini di un cammino minimo:

w(sv) = w(sy) + w(yv) = dsx+ w(x,y) + w(yv).

Poiché (u,v) minimizza dst+ w(t,z) per ogni tT e zT, allora:

dsx+ w(x,y) dsu+ w(u,v)

e quindi:

w(sv) ≥ dsu+ w(u,v) + w(yv)

e poiché w(yv) ≥ 0, ne segue dsv ≡ w(sv) ≥ dsu+ w(u,v), assurdo (avevamo supposto dsv < dsu+ w(u,v)). □



Approccio di Dijkstra

I nodi da aggiungere progressivamente a T sono mantenuti in una coda con priorità, associati ad un (unico) arco che li connette a T. Se y è in coda con arco (x,y) associato, e se analizzando (v,y) dopo aver aggiunto v a T risulta Dsv+w(v,y) < Dsx+w(x,y) , rimpiazziamo (x,y) con (v,y), ed aggiorniamo Dsy.

Dato un nodo u in T, scegli un nodo vT che minimizza la quantità Dsu+w(u,v)≡dsu+w(u,v)= dsv, aggiungi v a T ed effettua il passo di rilassamento su ogni nodo yT adiacente a v (per il quale cioè (v,y)E).



PseudocodiceNota: T è un albero che contiene tutti i nodi già aggiunti alla soluzione (ovvero quelli per i quali è già stato trovato il cammino minimo da s), più i nodi correntemente contenuti nella coda di priorità, ciascuno connesso al rispettivo nodo padre; non va confuso con l’albero T considerato nel lemma di Dijkstra!



Tempo di esecuzione: implementazioni elementari

Al più n insert, n deleteMin e m decreaseKey nella coda di priorità

• O(n log n+n+mn)=O(mn) con array ordinati

• O(n+n2+m log n)=O(n2+m log n) con array non ordinati

• O(n2 log n+n+m)=O(n2 log n) con liste ordinate

• O(n+n2+mn)=O(mn) con liste non ordinate

Insert DelMin DecKey

Array ordinato O(log n) O(1) O(n)

Array non ord. O(1) O(n) O(log n)

Lista Ordinata O(n) O(1) O(1)

Lista non ord. O(1) O(n) O(n)



Tempo di esecuzione: implementazioni efficienti

Al più n insert, n deleteMin e m decreaseKey nella coda di priorità

• O(n log n+n log n+m log n)=O(m log n) utilizzando heap (binari o binomiali)

• O(n+n log n+m)=O(m+n log n) con heap di Fibonacci

Insert DelMin DecKey

Heap binario O(log n)

O(log n) O(log n)

Heap Binom. O(log n)

O(log n) O(log n)

Heap Fibon. O(1) O(log n) O(1)



Esempio (1/2)



Esempio (2/2)



Approfondimento

Applicare l’algoritmo di Dijkstra con sorgente s sul seguente grafo:

s

a

c

b

d

5 1

34 5

1



Algoritmo di Floyd e Warshall(cammini minimi tra tutte le coppie di nodi

per tutti i grafi che non contengono cicli negativi)



Approccio• Elegante applicazione della tecnica della programmazione

dinamica

• Supponiamo di enumerare i vertici di G da 1 a n, cioè V={v1, v2, … vn}. Un cammino minimo k-vincolato da x a y è un cammino di costo minimo tra tutti i cammini da x a y che usano come vertici intermedi un sottoinsieme (anche vuoto) dei vertici {v1, v2, … vk}.

x=v1

7 1

4 3

y=v4

v2

v3

Tra x e y, il cammino minimo:• 0-vincolato è lungo +• 1-vincolato è lungo +• 2-vincolato è lungo 8: <x,v2,y>;• 3-vincolato è lungo 6: <x,v3,v2,y>;• 4-vincolato (ovvero senza vincoli) è lungo 6.

• Idea di Floyd e Warshall: calcolare cammini minimi k-vincolati per k=1,…, n

1



Relazioni tra distanze vincolate

L’algoritmo calcola dxy dal basso verso l’alto, incrementando k da 0 a n

• Sia dxy il costo di un cammino minimo k-vincolato da x a y. Chiaramente, valgono le seguenti proprietà:– dxy= w(x,y) se (x,y)E, +∞ altrimenti

– d

= d

e

d = d

– dxy= dxy

k

0

k-1

• Per le proprietà di cui sopra e per la proprietà di minimalità dei sottocammini di cammini minimi, si ha:

n

k kk-1xvk xvk vkxvkx



Pseudocodice

Tempo di esecuzione: (n3)

D: Come si confronta con l’applicazione ripetuta di Dijkstra?R: Utilizzando gli Heap di Fibonacci, n applicazioni dell’algoritmo di Dijkstra richiederanno tempo O(n (m+n log n))=O(nm+n2 log n)=O(n3). Quindi, Dijkstra è più efficiente. Tuttavia, si applica solo su un sottoinsieme delle istanze ammissibili per F&W.



Sommario graficoUniverso dei grafi

Grafi senza cicli negativi: BF e FW

Grafi senza archi negativi: Dijkstra

Grafi aciclici: ordinamento topologico



Approfondimento

Applicare l’algoritmo di Floyd e Warshall al seguente grafo:

s

a

c

b

d

5 -1

3-4 5

-1

Capitolo 13 Cammini minimi: Algoritmo di Dijkstra; Algoritmo di Floyd e Warshall Algoritmi e...

Documents

Transcript of Capitolo 13 Cammini minimi: Algoritmo di Dijkstra; Algoritmo di Floyd e Warshall Algoritmi e...