Algoritmi e Strutture Dati - cs.unicam.it13]algoritmiSuGrafi.pdf · Algoritmi e Strutture Dati...

Algoritmi e Strutture DatiAlgoritmi Elementari su Grafi

Maria Rita Di Berardini, Emanuela Merelli1

1Dipartimento di Matematica e InformaticaUniversita di Camerino

A.A. 2006/07

Di Berardini, Merelli Algoritmi e Strutture Dati

Visita in Profondita

Parte I

Visite su Grafi



Visita in Profondita (depth-first search, DFS)

La strategia adottata da questo schema di visita consiste nel visitare ilgrafo sempre piu in “profondita” (fin quando e possibile)

Si comincia con il visitare un nodo qualsiasi v che viene marcato come“scoperto”

La visita prosegue ispezionando tutti gli archi uscenti dal nodo corrente valla ricerca di un nodo w collegato ad v e non ancora visitato

Se tale nodo esiste, diventa il prossimo nodo corrente (viene marcatocome “scoperto” e si ripente il passo precedente)

Prima o poi, si arriva ad un punto in cui tutti gli archi incidenti il nodo

corrente v portano a nodi visitati




In questo caso siamo costretti a fare un passo indietro (“backtrack”),tornando al nodo u visitato prima di v ; u diventa il nodo corrente e siripetono i passi precedenti

2 3

4 5

61

Lo schema di visita in profondita (a partire dal nodo 1) visita, nell’ordine

1, 2, 3, 6 (backtrack) 5 (backtrack, due volte) 4




Proprio come la visita in ampiezza, colora i nodi per distinguere i nodi nonancora scoperti (WHITE), da quelli scoperti ma non espansi (GRAY) e daquelli espansi (BLACK)

Di nuovo ad ogni nodo v viene associato un precedessore denotato con π[v ], eil nodo che ci consente di raggiungere v durante la visita

Inoltre, ogni nodo v ha associate due informazioni temporali:

il tempo di scoperta d [v ] registra il momento in cui il nodo viene scoperto(e diventa grigio)

il tempo di completamento f [v ] registra il momento in cui la visitacompleta l’ispezione della lista di adiacenza di v (ed il nodo diventa nero)

Per ogni nodo v abbiamo che d [v ] < f [v ]; inoltre: v e WHITE prima di d [u], e

GRAY tra d [u] e f [u], e BLACK successivamente




DFS(G )

1. foreach nodo u ∈ V [G ]2. do color [u]←WHITE3. π[u]← NIL4. time ← 0

. time e una variabile globale usata per calcolare i tempi d [u] e f [u]

5. foreach nodo u ∈ V [G ]6. do if color [u] = WHITE7. then DFS-visit(u)

N.B: Il risultato della visita potrebbe dipendere dall’ordine con cui i nodivengono ispezionati nella riga 5

In realta, queste differenze nell’ordine non causano problemi, perche tutti i

possibili risultati della visita sono sostanzialmente equivalenti




DFS-visit(u)

1. color [u]← GRAY2. time ← time + 13. d [u]← time4. foreach nodo v ∈ Adj [u]5. do if color [v ] = WHITE . ispezioniamo l’arco (u, v)

6. then π[v ]← u7. DFS-visit(u)8. color [u]← BLACK9. time ← time + 110. f [u]← time




Nella fase di inizializzazione, tutti i nodi vengono colorati di bianco ed illoro predecessore viene settato a NIL; la variabile globale time vienesettato a zero

DFS-visit(u) visita (in profondita) tutti i nodi raggiungibili da u

Quando DFS finisce, ogni vertice u ha associato un tempo di scoperta

d [u] e un tempo di completamento f [u]



Visita in Profondita – un esempio

1/

u v

x y

w

z

1/

u

2/

v

x y

w

z

1/

u

2/

v

x

3/

y

w

z

1/

u

2/

v

4/

x

3/

y

w

z




1/

u

2/

v

4/5

x

3/

y

w

z

1/

u

2/

v

4/5

x

3/6

y

w

z

1/

u

2/7

v

4/5

x

3/6

y

w

z

1/8

u

2/7

v

4/5

x

3/6

y

w

z




1/8

u

2/7

v

4/5

x

3/6

y

9/

w

z

1/8

u

2/7

v

4/5 3/6

9/

w

10/

x y z

1/8

u

2/7

v

4/5 3/6

9/

w

10/11

x y z

1/8

u

2/7

v

4/5 3/6

9/12

w

10/11

x y z



Visita in Profondita – complessita

Quale e il tempo di esecuzione di DFS? Il ciclo di righe 1-3 impiegano untempo O(n). Quanto ci costa eseguire ciascun chiamata di DFS-Visit?

La procedura DFS-Visit viene eseguita esattamente una volta per ognivertice v ∈ V (viene invoca solo se il colore e WHITE e la prima cosa chefa e cambiare il colore degli archi in GRAY)

Durante un’esecuzione di DFS-Visit, il ciclo delle righe 4-7 vieneeseguito |Adj [u]| volte. Poiche∑

v∈V

|Adj [u]| = O(m)

dove m = |E |, il costo totale per le chiamate di DFS-Visit e O(m).

Quindi il costo totale dell’algoritmo e O(n + m)



Sottografo dei predecessori

Il sottografo dei predecessori e definito in modo leggermentediverso da BFS

Gπ = (V ,Eπ)Eπ = {(π[v ], v) : v ∈ V and π[v ] 6= NIL}

Gπ forma una foresta depth-first perche, in generale, e compostada vari alberi depth-first

1/8

u

2/7

v

4/5 3/6

9/12

w

10/11

x y z


Definizione del problemaAlgoritmo di Kruskal

Algoritmo di Prim

Parte II

Minimo Albero Ricoprente



Algoritmo di Prim

Minimo albero ricoprente

Sia G = (V ,E ) un grafo non orientato, connesso e pesato (w : E → R ela funzione peso, dove R e l’insieme dei numeri reali)

Assumiamo che i nodi rappresentino delle citta, un generico arco (u, v)un possibile collegamento tra le citta u e u, e w(u, v) il costo dellacostruzione di tale collegamento

Problema: cercare un insieme T di strade/archi tale che ogni citta siaraggiungibile da ogni altra (il sottografo G ′ = (V ,T ) e quindi connesso)e tale da minimizzare la somma dei costi di costruzione (la somma deicosti associati agli archi)

Se i pesi associati agli archi sono positivi G ′ e senza cicli e quindi e un

albero (G ′ e connesso e senza cicli)



Algoritmo di Prim

Minimo albero ricoprente

Questo problema e noto come problema del minimo albero ricoprente(minimum spanning tree, MST)

Si noti che in generale, la soluzione di questo problema non e unica

2

31

2

2

12

31

2 12

31 2

1

Esamineremo due algoritmi golosi per risolvere il problema del minimo

albero ricoprente: l’algoritmo di Kruskal e l’algoritmo di Prim



Algoritmo di Prim

Algoritmo di Kruskal



Algoritmo di Prim


Ordina gli archi secondo costi crescenti e costruisce un insieme ottimo diarchi T scegliendo di volta in volta un arco di peso minimo che nonforma cicli con gli archi gia scelti

Per far questo, gestisce una partizione W = {W1,W2, . . . ,Wk} di V ,insieme dei nodi del grafo, in cui ogni Wi rappresenta un insieme di nodiper cui e stato scelto un insieme di archi che li collega

Inizialmente, T = ∅ e W = {{1}, {2}, . . . , {n}}, poiche nessun arco estato scelto e, quindi, nessun nodo e stato collegato

Alla prima iterazione viene scelto il nodo (u, v) di peso minimo; questo

viene posto in T (T e vuoto e quindi l’inserimento di (u, v) non puo

formare cicli) e gli insiemi {u} e {v} vengono sostituiti con l’insieme

{u, v}



Algoritmo di Prim


Alla generica iterazione i , esaminiamo l’arco (x , y) con i-esimo costo cheviene aggiunto alla soluzione T solo se i nodi x e y non appartengonoallo stesso insieme della partizione W (cioe se l’arco non forma cicli congli archi inseriti in precedenza)

In questo caso, dopo aver inserito l’arco (x , y) in T , si sostituiscono nella

partizione W gli insiemi (distinti) contenenti x e y con la loro unione



Algoritmo di Prim

Algoritmo di Kruskal – un esempio

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10



Algoritmo di Prim

Algoritmo di Kruskal – un esempio

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

Soluzione ottima



Algoritmo di Prim


MST-Kruskal(G , w)

1. T ← ∅2. foreach nodo v ∈ V [G ]3. do Make-Set(v) . costruisce W = {{1}, {2}, . . . , {n}}

4. ordina gli archi di E in senso non decrescente rispetto al peso w5. foreach arco (u, v) ∈ E [G ] preso in ordine non decrescente di peso6. do if Find-Set(u) 6= Find-Set(v)7. then T ← T ∪ {(u, v)}8. Union-Set(u, v)9. return T

dove:

Find-Set(x) restituisce, per ogni nodo x , l’indice di W contenente x

Union-Set(u, v) costruisce l’unione di Find-Set(u) e Find-Set(v)



Algoritmo di Prim

Algoritmo di Kruskal – complessita

L’ordinamento di m = |E | archi richiede O(m log2 m) passi. Il costo dellem iterazioni del ciclo di riga 5 dipende dal costo delle uniche operazioninon costanti, ossia Find-Set e Union-Set

In Hopcroft-Ullman viene presentata una struttura dati che rappresenta lapartizione W come un insieme di alberi bilanciati

Questa struttura dati permette di eseguire una qualunque sequenza di cm(con c costante) operazioni di unione e ricerca su insiemi aventicomplessivamente m elementi, in un tempo O(m g(m)) dove g(m) e unafunzioe tale che g(m) = O(log2 m)

Possiamo quindi concludere che il costo complessivo dell’algoritmo e

O(m log2 m) = O(m log2 n2) = O(m log2 n) dove n = |V | e il numero di

nodi



Algoritmo di Prim

Algoritmo di Kruskal – correttezza

Sia G = (V ,E ) un grafo non orientato, non connesso e pesato:

1 un taglio di G e una partizione (S ,S = V − S) dell’insieme V deinodi

2 diciamo che un arco (u, v) attraversa un taglio (S ,S) se una delledue estremita si trova in S e l’altra in S

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

Il taglio (S={a, b, d, e}, V-S) è attraversato dagli archi

(a,h), (b, h), (b, c), (c, d), (f, d) e (f, e)

L’arco che attraversa il taglio dicosto minimo – arco leggero – è

l’arco (c,d)



Algoritmo di Prim


Teorema 1: sia

G = (V ,E ) un grafo non orientato, non connesso e pesato;

(S ,S) un taglio di G ;

T un’insieme di archi corrispondenti ad una soluzione ottima, ossiaT e tale che G ′ = (V ,T ) e un MST.

Un arco (u, v) di peso minino fra tutti quelli che attraversano (S ,S) (unarco leggero) fa parte della soluzione ottima T

u

x

v

1

y

21

1

3 1

1

1

3

2



Algoritmo di Prim


Proviamo la correttezza dell’algoritmo di Kruskal mostrando come, ad ogniiterazione, questo algoritmo inserisce in T un “pezzo” di soluzione ottima

Sia T l’insieme di archi costruito da Kruskal appena prima di inserire l’arco(u, v). Allora:

gli archi in T partizionano il grafo G in una o piu componenti connesse

ogni elemento Wi della partizione W = {W1, W2, . . . , Wk} e uninsieme di nodi per cui e stato scelto un’insieme di archi che licollega, ossia, e una componente connessa del grafo

inoltre, i nodi u e v appartengo a due componenti diverse e questo percheFind-Set(u) 6= Find-Set(v))

Consideriamo ora il taglio che (Wi , Wi = V −Wi ) dove Wi e l’elemento di W

tale che u ∈Wi . L’arco (u, v) (ossia il prossimo arco scelto da Kruskal) e un

arco di peso minimo che attraversa il taglio (Wi , Wi ). Per il Teorema 1, (u, v)

e parte di una soluzione ottima



Algoritmo di Prim

Algoritmo di Prim



Algoritmo di Prim

Algoritmo di Prim

E essenzialmente un algoritmo di visita che, partendo da un nodo inizialeu (scelto arbitrariamente) esamina tutti i nodi del grafo

Analogamente agli algoritmi di visita, ad ogni iterazione, partendo da unnodo v , visita un nuovo nodo w (scelto secondo opportuni criteri) e ponel’arco (v ,w) nell’insieme T che, al termine dell’esecuzione, conterra unasoluzione ottima

La differenza sostanziale rispetto ad un algoritmo di visita “standard”, eche la scelta del prossimo nodo da visitare viene fatta introducendo unconcetto di priorita tra nodi e che l’insieme Q dei nodi da visitare vienegestito come una coda di priorita

Se R e l’insieme dei nodi visitati, la priorita di un nodo v ∈ Q e pari al

minimo peso di un arco che collega v con un nodo in R



Algoritmo di Prim

Algoritmo di Prim

Durante la generica iterazione, l’algoritmo estrae dalla coda Q dei nodida visitare, il nodo v con priorita minima e inserisce in T (la soluzionecorrente) l’arco (u, v) che risulta di peso minimo tra tutti quelli checollegano v con un nodo in R

L’iterazione termina aggiornando le priorita dei nodi non visitati collegati

con v



Algoritmo di Prim

L’algoritmo di Prim

MST-Prim(G ,w , r). w e la funzione peso ed r e il nodo da cui parte la visita

1. foreach nodo v ∈ V [G ]2. do key [v ] =∞ . setta le priorita iniziali

3. π[v ] = NIL . inizializza il vettore dei predecessori

4. key [r ]← 05. Q ← V [G ]6. while Q 6= ∅7. do u ← Extract-Min(Q)8. for each v ∈ Adj [u]9. do if v ∈ Q and w(u, v) < key [v ]10. then π[v ]← u11. key [v ]← w(u, v)



Algoritmo di Prim

Algoritmo di Prim – un esempio

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

0 ∞ ∞ ∞ ∞ ∞ ∞a b c d e f g

∞ ∞h i

4 ∞ ∞ ∞ ∞ ∞ 8 ∞

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

8 ∞ ∞ ∞ ∞ 8 ∞a b c d e f g h i

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

7 ∞ 4 ∞ 8 2a b c d e f g h i



Algoritmo di Prim


b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

7 ∞ 4 6 7a b c d e f g h i

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

7 10 2 7a b c d e f g h i

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

7 10 7a b c d e f g h i



Algoritmo di Prim


b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

7 10a b c d e f g h i

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

9a b c d e f g h i

b c

h g

d

a

f

ei8

4

11

8

1 2

67

2 4

7

14

9

10

a b c d e f g h i



Algoritmo di Prim

Algoritmo di Prim – Complessita

La fase di inizializzazione (righe 1-5) puo essere eseguita in un tempoO(n), dove n = |V |

Il costo del ciclo while (riga 6) (ciclo ripetuto n volte) e dato da:

il costo di estrazione del minimo ⇒ se Q e implementata come unmin-heap questa operazione puo essere implementata con un costopari a O(log2 n)

+

costo del ciclo for (righe 8-11)



Algoritmo di Prim


Per ogni u ∈ Q, il ciclo for (righe 8-11) viene eseguito αu volte, dove conαu abbiamo indicato la lunghezza della lista di adiacenza di u. Inoltre:

Il test del di verifica di appartenenza a Q puo essere fatto in tempocostante (mantenendo un bit per ogni vertice che dica se quel nodoappartiene o meno a Q – bit che viene aggiornato quando togliamoun nodo da Q)

l’assegnamento di riga 11 richiede implicitamente un operazioneDecrease-Key che puo essere implementata (usando di nuovo unmin-heap) in un tempo O(log2n)

Il costo di ogni iterazione ciclo for e O(αu log2 n)



Algoritmo di Prim


La fase di inizializzazione (righe 1-5) puo essere eseguita in un tempoO(n), dove n = |V |

Il costo del ciclo while (riga 6) e dato da:

il costo di estrazione del minimo ⇒ se Q e implementata come unmin-heap questa operazione puo essere implementata con un costopari a O(log2 n)

+

costo del ciclo for (righe 8-11) = O(αu log2 n)

Riassumendo, il costo del ciclo while ≤∑

u∈V

O(αu log2 n + log2 n)



Algoritmo di Prim


Il costo del ciclo while∑u∈V

O(αu log2 n + log2 n) = O(∑u∈V

αu log2 n + log2 n) =

O(log2 n∑u∈V

(αu + 1)) = O(log2 n (

∑u∈V

αu + n))

=

O(log2 n (2m + n)

)= O

(log2 n (m + n)

)Il costo complessivo dell’algoritmo e

O(log2 n (m + n) + n

)= O(log2 n (m + n)) = O(m log2 n)


Parte III

Cammini Minimi


Definizione e proprieta

Sia G = (V ,E ) un grafo orientato e pesato, con una funzione di pesow : E → R, definiamo:

il peso di un cammino p = 〈v0, v1, . . . , vn〉 come la somma dei pesidegli archi che lo compongono

w(p) =n∑

i=1

w(vi−1, vi )

il peso di un cammino minino da u a v come

δ(u, v) =

{min{w(p) : u

p v} se esiste un cammino da u a v

∞ altrimenti

Esamineremo il problema dei cammini minimi da sorgente unica: trovare

il cammino minimo da un nodo sorgente s a ciascun nodo v ∈ V


Varianti

Cammino minimo con destinazione unica: trovare un cammino minimoda ciascun nodo v ad un dato nodo destinazione t (puo esserericondotto al problema del cammino minimo da sorgente unica invertendoil senso degli archi)

Cammino minimo per una coppia di nodi: trovare un cammino minimoda u a v , noti i vertici u e v (basta risolvere il problema dei camminiminimi con sorgente u)

Cammino minimo per ogni coppia di nodi: trovare un cammino minimo

da u a v per ogni coppia di nodi u e v (basta risolvere il problema dei

cammini minimi per ogni nodo u del grafo)


Sottostruttura ottima del problema del cammino minimo

Dati un grafo orientato e pesato G = (V ,E ), con una funzione di pesow : E → R, sia p = 〈v0, v1, . . . , vk〉 un cammino minimo tra i nodi v1 e vk

Per ogni 1 ≤ i ≤ j ≤ k, il sottocammino pij = 〈vi , vi+1, . . . , vj〉 e uncammino minimo da vi a vj

Proof: se scomponiamo il cammino p in v1p1i vi

pij vj

pjk vk abbiamo

che w(p) = w(p1i ) + w(pij) + w(pjk)

Assumiamo ora che esista un cammino p′ij con peso w(p′ij) < w(pij) (equindi che w(pij) non sia ottimo)

Allora il cammino p′ = v1p1i vi

p′ij vj

pjk vk ha peso

w(p′) = w(p1i ) + w(p′ij) + w(pjk) < w(p)

il che contraddice il fatto che p e ottimo


Archi di peso negativo

La funzione w puo assegnare dei pesi negativi agli archi; tuttavia, nelcaso in cui dalla sorgente s e possibile raggiungere un ciclo con pesonegativo (il peso di un ciclo e la somma dei pesi dei suoi archi), il pesodei cammini minimi non e ben definito


Cammini minimi e cicli

Un cammino minimo puo contenere dei cicli? Abbiamo appena visto chenon puo contenere cicli con peso negativi

Non puo neanche contenere cicli con pesi positivi, altrimenti non sarebbeminimo

w(c) ≥ 0

Infine e sempre possibile eliminare cicli di peso 0 senza alterare il peso delcaamini, che se era minimo rimane minimo

Possiamo assumere che un cammino minimo non contenga cicli; quindi

un cammino minimo in un grafo G = (V ,E ) puo avere al piu n− 1 (dove

n = |V |) archi


Rappresentazione dei cammini minimi

Spesso e utile calcolare non solo i cammini minimi ma anche i vertici checompongono tali cammini

Dato G = (V ,E ), manteniamo per ogni vertice v un predecessore π[v ]che po essere un altro nodo o NIL

L’algoritmo di Dijkstra (algoritmo per il calcolo dei cammini minimi dasorgente unica a che studieremo) gestisce π in maniera t.c. la catena deipredecessori che parte da v ripercorra all’indietro il cammino minimo da sa v

L’albero dei predecessori Gπ = (Vπ,Eπ) indotto da π e definito come :

Vπ = {v ∈ V : π[v ] 6= NIL} ∪ {s}Eπ = {(π[v ], v) ∈ E : v ∈ Vπ − {s}}

Gπ e tale che ogni cammino da s a v in Gπ corrisponde ad un cammino

minimo s a v in G


Rilassamento

L’algoritmo di Dijkstra usa una tecnica che prende il nome di tecnica delrilassamento

Questa tecnica consiste nel memorizzare, per ogni nodo v del grafo, unattributo d [u] (stima del cammino minimo) che rappresenta un limitesuperiore al peso del cammino da s a v (limite che viene rilassato ognivolta che viene trovata una strada “migliore”)

La seguente procedura inizializza le stime dei cammini minimi e il vettoredei predecessori in un tempo O(n) (n e sempre il numero dei nodi)

Initialize-Single-Source(G , s)

1. for each v ∈ V [G ]2. do d [u]←∞3. π[v ]← NIL4. d [s]← 0


Rilassamento

Il processo di rilassamento di un arco (u, v) consiste nel verificare sepassando per u e possibile migliorare la stima del cammino minimo per ve in caso affermativo nell’aggiornare i valori di d [u] e π[u]

5 9

u v2

5 72

u v

Relax(u, v ,w)

1. ifd [v ] > d [u] + w(u, v)2. then d [v ]← d [u] + w(u, v)3. π[v ]← u


Algoritmo di Dijkstra

Risolve il problema dei cammini minimi a sorgente unica (indicata con s)in un G = (V ,E ) orientato e con pesi sugli archi non negativi (per ogniarco (u, v) ∈ E , il peso w(u, v) ≥ 0)

Mantiene un insieme di nodi S i cui pesi dei cammini minimi da s sonogia stati determinati

Seleziona ripetutamente il nodo in u ∈ V − S con la minima stima del

cammino minimo (Dijkstra e un algoritmo goloso) e rilassa tutti gli archi

che escono da u


Algoritmo di Dijkstra – un esempio

∞ ∞

∞ ∞

0

5

103

1

2

9

2 6 4s

y z

t x

7

10 ∞

5 ∞

0

5

103

1

2

9

2 6 4s

y z

t x

7

8 ∞

5 7

0

5

103

1

2

9

2 6 4s

y z

t x

7

8 13

5 7

0

5

103

1

2

9

2 6 4s

y z

t x

7


Algoritmo di Dijkstra – un esempio

8 13

5 7

0

5

103

1

2

9

2 6 4s

y z

t x

7

8 9

5 7

0

5

103

1

2

9

2 6 4s

y z

t x

7

8 9

5 7

0

5

103

1

2

9

2 6 4s

y z

t x

7


Algoritmo di Dijkstra

Risolve il problema dei cammini minimi a sorgente unica (indicata con s)in un G = (V ,E ) orientato e con pesi sugli archi non negativi (per ogniarco (u, v) ∈ E , il peso w(u, v) ≥ 0)

Mantiene un insieme di nodi S i cui pesi dei cammini minimi da s sonogia stati determinati

Seleziona ripetutamente il nodo in u ∈ V − S con la minima stima delcammino minimo (Dijkstra e un algoritmo goloso) e rilassa tutti gli archiche escono da u

L’insieme Q dei nodi non in S (Q = V − S) viene gestito come una coda

di min-priorita, utilizzando i valori di d come chiavi


Algoritmo di Dijkstra – complessita

Dijkstra(G ,w , s)

1. Initialize-Single-Source(G , s)2. S ← ∅3. Q ← V [G ]4. while Q 6= ∅5. do u ← Extract-Min(Q)6. S ← S ∪ {u}7. foreach v ∈ Adj [u]8. do Relax(u, v ,w)



Poiche l’insieme Q viene gestito come una coda di priorita, il costo diDijkstra dipende da come implementiamo la coda e quindi dal costodelle operazioni Insert (implicita nella riga 3), Extract-Min (riga 5) eDecrease-Key (implicita in Relax di riga 8)

Assumiamo che la coda viene implementata semplicemente come unarray di n elementi:

Insert e Decrease-Key hanno un costo costante – O(1)

Extract-Min ha un costo O(n) – possiamo solo scandire l’array



Ora, osserviamo che il ciclo while di riga 4 viene eseguito esattamente nvolte; inoltre:

ciascuna iterazione ha un costo dato dalla chiamata di Extract-Min piu ilcosto della scansione della lista di adiacenza del nodo u appena inserito inS

poiche ogni nodo viene inserito in S solo una volta, ogni lista di adiacenzaviene scandita esattamente una volta

Il costo del ciclo while e dato dal costo del n di Extract-Min piu il costodella scansione delle liste, ossia O(n2 + m) = O(n2)

A questo costo va aggiunto il costo della fase di inizializzazione di riga 1;quindi il tempo richiesto dall’algoritmo e dell’ordine di

O(n2 + n) = O(n2)


Algoritmi e Strutture Dati - cs.unicam.it13]algoritmiSuGrafi.pdf · Algoritmi e Strutture Dati...

Documents

Transcript of Algoritmi e Strutture Dati - cs.unicam.it13]algoritmiSuGrafi.pdf · Algoritmi e Strutture Dati...