Algoritmi e Strutture dati Mod B Grafi: Percorsi Minimi (parte I)

Algoritmi e Strutture dati Mod B

Grafi: Percorsi Minimi

(parte I)

Grafi: Percorsi minimi

Un percorso minimo in un grafo G=<V,E> grafo pesato orientato, con funzione di peso w: E che mappa archi in pesi a valori reali tra due vertici s e v, è un percorso da s a v tale che la somma dei pesi degli archi che formano il percorso sia minima. 1

2 3 4

5 5

101

5

4

3

31

2

61

1

8

v

s

Percorsi minimi: pesi negaivi

w6

7

9

-5

-4

xy

v

u 8 7

-2

-3

Qual’è il percorso minimo tra u e x nel grafo sottostante?

Percorso Peso

<u,v,x> 2

<u,v,w,v,x> -5 <u,v,w,v,w,v,x> -12<u,v,w,v,w,v,w,v,x> -19 … ... … ...

Non esiste alcun percorso minimo tra u e x!


Lemma 1: Dato un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali, sia p=<v1,…,vk> il percorso minimo tra v1 e vk e per ogni i e j con 1 i j k, sia pij=<vi,…,vj> un sottopercorso di p tra vi e vj. Allora, pij=<vi,…,vj> è un percorso minimo tra vi e vj.

Proprietà di sottostruttura ottima(per dimostrazione vedere Cormen)


Corollario 1: Sia G = (V, E) un grafo pesato orientato, con funzione di peso w: E che mappa archi in pesi a valori reali. Supponiamo che un percorso minimo p dalla sorgente s ad un veritce v possa essere decomposto in suv per qualche vertice u e percorso p’. Allora, il peso del percorso minimo tra s e v è (s,v)= (s,u) + w(u,v).

p’

Lemma 2: Dato un grafo pesato orientato G = (V, E), con funzione di peso w: E , e un vertice sorgente s, allora per ogni arco (u,v) in E vale (s,v) (s,u) + w(u,v).

Per dimostrazioni vedere Cormen

Albero dei percorsi minimi

Definizione: Sia G = (V, E) un grafo pesato orientato, con funzione di peso w: E che mappa archi in pesi a valori reali. Un albero dei percorsi minimi con radice s è un sottografo orientato G’ = (V’, E’) di G con V’ V e E’ E e tale che:

V’ è l’insieme di vertici raggiungibili da sG’ forma un albero radicato in sper ogni vV’ , l’unico percorso semplice da s a

v è un percorso minimo.


• Peso unitario• Breadth First Search

• Pesi non negativi• Algoritmo di Dijkstra

• Pesi non negativi con cicli non negativi• Algoritmo di Bellman-Ford

• Cicli negativi• Nessuna soluzione

Grafi: Percorsi minimi (Dijkstra)

1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

Sia dato un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali.

1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

Il peso di un percorso p = (v1 , v2 , . . ., vk )è

w(vi , v

i+1).

i=1

k-1

Il peso del percorso lungo gli archi rossi è 1 + 6 + 1 + 4 = 12.

Grafi: Percorsi minimi (Dijkstra)Sia dato un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali.

1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

Problema del percorso minimo da una singola sorgente: dato un ver-tice s, per ogni vertice v V trovare un percorso minimo da s a v.

Grafi: Percorsi minimi (Dijkstra)Sia dato un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali.

Il peso di un percorso p = (v1 , v2 , . . ., vk )è

w(vi , v

i+1).

i=1

k-1

1

2 3 4

6 5

101

5

4

3

31

2

61

1

8L’algoritmo di Dijkstra risol-ve il problema in modo effi-ciente nel caso in cui tutti i pesi siano non-negativi, come nell’esempio del grafo.



1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

L’algoritmo di Dijkstra risolve il problema in modo efficiente nel caso in cui tutti i pesi siano non-negativi, come nell’esem-pio del grafo.- Utilizza un campo d[v] con la stima della distanza minima- Utilizza un campo p[v] con il nodo predecessore di v



Sottografo dei predecessori (Dijkstra)

• L’algoritmo di Dijkstra sul grafo G=<V,E>

costruisce in p[] il sottografo dei predecessori denotato con Gp=<Vp,Ep>, dove:

Vp = { v V : p [v] Nil} {s}

Ep = { (p [v],v) E : v Vp - {s} }

Il sottografo dei predecessori è definito come per BFSLa differenza è che ora verrà costruito in modo che i percorsi che individua siano quelli con peso minimo (non col numero minimo di archi)

Si dimostra che il sottografo dei predecessori costruito dall’algoritmo di Dijkstra è un albero dei percorsi minimi

1

2 3 4

6 5

101

5

4

3

31

2

61

1

8


Inizializzazione del grafo

1 La stima distanza d[s] viene posta a 0 2 Tutte le altre stime delle disanze d[v]) sono posti a

Inizializza(G,s)

1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

1 La stima distanza d[s] viene posta a 0 2 Tutte le altre stime delle disanze d[v]) sono posti a 3 I predecessori p[v] sono posti a Nil


Inizializzazione del grafo

0

Inizializza(G,s)


1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

Meccanismo di aggiustamento (diminuzione) progressivo delle stime d[v] delle distanze minime tra s e gli altri nodi v.

Rilassamento degli archi

Utilizza la funzione di peso w e si applica agli archi del grafo. Modifica sia d[v] che p[v].

Rilassamento

1

3

v

u

5

1

3

v

u

4

Relax(u,v,w)

1

8

z

u

10

1

8

z

u

9

Relax(u,z,w)

1

1

x

u

Relax(u,x,w)

1

1

x

u

2

5

4

0

10 1 5

101

3

31

2

61

1

8u

x

z

v

0

9 1 4

2

101

5

4

3

31

2

61

1

8u

x

z

v

Rilassamento

2

4

v

u

4

2

4

v

u

4

Relax(u,v,w)

0

9 1 4

11 2

101

5

4

3

31

2

61

1

8

u

v

z0

9 1 4

4 2

101

5

4

3

31

2

61

1

8

u

v

z

2

2

z

u

11

2

2

z

u

4

Relax(u,z,w)

Rilassamento

Verifica se è possibile ottenere un percorso migliore tra s e v passando per il vetice u

• d[v]: estremo superiore della lunghezza del percorso minimo tra s a v (s è la sorgente)

• p[v]: il vertice predecessore di v nel percorso minimo corrente tra s e v (padre di v)

• w(u,v): peso dell’arco (u,v)

Relax(u,v,w) if d[v] > d[u] + w(u,v) then d[v] = d[u] + w(u,v) p[v] = u

Rilassamento: proprietà

Lemma 3: Sia dato un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali e sia (u,v)E. Allora, immediatamente dopo un rilas-samento di (u,v) (Relax(u,v,w)), otteniamo che d[v] d[u] + w(u,v).


Lemma 4: Sia dato un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali. Sia s la sorgente e il grafo sia inizializzato con una chiamata a Inizializza(G,s). Allora, vale d[v] (s,v) per ogni vertice v di G e tale invariante viene mantenuto lungo ogni sequenza di operazioni di rilassamento. Inoltre, appena d[v] = (s,v), d[v] non cambia più.


Corollario 2: Sia dato un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali. Suppeoniamo che in G non esistano percorsi tra s e un vertice v. Allora dopo che grafo è stato inizializzato con Inizializza(G,s), vale d[v] = (s,v) e questa uguaglianza viene mantenuto lungo ogni sequenza di operazioni di rilassamento.


Lemma 5: Sia dato un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali. Sia s la sorgente e suv sia un percorso minimo per qualche u,vV. Il grafo sia inizializzato con una chiamata a Inizializza(G,s) e venga applicata una sequenza di operazioni di rilassamento che includa Relax(u,v,w).

Se, d[u] = (s,u) in qualunque momento prima della chiamata, allora vale d[v] = (s,v) sempre dopo la chiamata.

Rilassamento e percorsi minimi

Lemma 6: Sia dato un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali e sia s la sorgente.

Allora, dopo che il grafo è stato inizializzato con una chiamata a Inizializza(G,s), il sottografo dei predecessori Gp forma un albero con radice s, e qualunque sequenza di opra-zioni di rilassamento su G mantiene questa proprietà.


Lemma 7: Sia dato un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali. Sia s la sorgente e G non contenga cicli di peso negativo.

Il grafo sia inizializzato con una chiamata a Inizializza(G,s) e venga applicata una sequenza di operazioni di rilassamento che includa Relax(u,v,w) tale che d[v] = (s,v).

Allora il sottografo dei predecessori Gp è un albero di cammini minimi con radice s.

1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

L’algoritmo di Dijkstra utilizza un insieme S di vertici i cui pesi del percorso minimo sono già stati determinati.

Utilizza anche, per ogni ver-tice v non in S, un campo d[v] contenente ad ogni passo l’estremo superiore del peso del percorso minimo da s a v.


1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

L’algoritmo seleziona a turno il vertice u in V – S col minimo valore d[u], inserisce u in S, e rilassa tutti gli archi uscenti da u.


Utilizza anche, per ogni ver-tice v non in S, un campo d[v] contenente ad ogni passo l’estremo superiore del peso del percorso minimo da s a v.


1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

Inizialmente: S = { }.

1 2 3 4 5 6

0

v

d

Inizializza una coda a priorità con tutti i vertici e i loro estremi superiori d[].

Sia 1 il verticesorgente.



1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

1 2 3 4 5 6

0

v

d

Seleziona il vertice u V – S con il minimo valore d[v], inserisce u in S, . . .


Inizialmente: S = { }.



1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

v

d

. . . rimuovi u dalla coda, inserisci u in S,. . .

2 3 4 5 6

1

0S = (qui manteniamo la stima

con il vertice in S)




1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

2 3 4 5 6

10 1 5

v

d

. . . e rilassa gli archi uscentida u.

1

0




1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

23 4 5 6

101 5

v

d

. . . riordina la coda rispetto alle nuove stime.

1

0




1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

Ripeti . . .


S =

23 4 5 6

101 5

v

d

1

0



1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

24 5 6

105

v

d

. . . rimuovi dalla coda einserisci in S

1

0

3

1




1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

24 5 6

94 2

v

d

. . . rilassa gli archi . . .

3

1

1

0




1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

245 6

942

v

d

. . . e riordina la coda. . .

3

1

1

0




1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

245 6

942

v

d

3

1

1

0

Ripeti . . .




1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

24

5

6

94

2

v

d

3

1

1

0





1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

24

5

6

94

2

4

v

d

3

1

1

0





1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

24

5

6

94

2

4

v

d

3

1

1

0


. . . e riordina la coda. . .



1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

24

5

6

94

2

4

v

d

3

1

1

0


Ripeti . . .



1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

2

54

6

9

24

4

v

d

3

1

1

0





1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

2

54

6

9

24

4

v

d

3

1

1

0

. . . e riordina la coda (nessun cam-biamento in questo caso) . . .




1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

2

54

6

9

24

4

v

d

3

1

1

0


Ripeti . . .



1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

2

54 6

9

24 4

v

d

3

1

1

0





1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

2

54 6

9

24 4

v

d

3

1

1

0

. . . rilassa gli archi (nessun cam-biamento in questo caso) . . .




1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

2

54 6

9

24 4

v

d

3

1

1

0


Ripeti . . .



1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S = 2 54 6

9 24 4

v

d

3

1

1

0

Fatto!




1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

Il risultato è la riga in basso che contiene in ciascuna cella la lunghezza del percorso minimo dal nodo s al nodo indicato nella riga sopra.

v

d

2 54 6

9 24 4

3

1

1

0




1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

Per calcolare i percorsi corris-pondenti, utilizziamo il campo p[v], che contiene il predeces-sore v lungo il percorso minimo.

v

d

2 54 6

9 24 4

3

1

1

0

3 1 3 3 5p


1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

Utilizzando il predecessore p[v], si può facilmente ricostruire il percorso fino a v, procedendo all’indietro da v a s.

v

d

2 54 6

9 24 4

3

1

1

0

3 1 3 3 5p


1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

Es., v = 6.

v

d

2 54 6

9 24 4

3

1

1

0

3 1 3 3 5p


1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

Es., v = 6. p(6) = 5,

v

d

2 54 6

9 24 4

3

1

1

0

3 1 3 3 5p


1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

Es., v = 6. p(6) = 5, p(5) = 3,

v

d

2 54 6

9 24 4

3

1

1

0

3 1 3 3 5p


1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S =

Es., v = 6. p(6) = 5, p(5) = 3, p(3) = 1.

v

d

2 54 6

9 24 4

3

1

1

0

3 1 3 3 5p


1

2 3 4

6 5

101

5

4

3

31

2

61

1

8

s

S = v

d

2 54 6

9 24 4

3

1

1

0

3 1 3 3 5p

Percorso: 1, 3, 5, 6.Peso: 4.


Es., v = 6. p(6) = 5, p(5) = 3, p(3) = 1.

L’algoritmo di Dijkstra

Dijkstra(G,s) Inizializza(G,s) S = Q = V(G) while ( Q ) u = Delete_Min(Q) S = S {u} for each vertice v adiecente a u relax(u,v,w)

Coda di priorità

L’algoritmo di Dijkstra

Dijkstra(G,s) Inizializza(G,s,d) S = Q = V(G) while ( Q ) u = Delete_Min(Q) S = S {u} for each vertice v adiecente a u relax(u,v,w)

Coda di priorità

Relax(u,v,w) if d[v] > d[u] + w(u,v) then Decrase_key(d[v], d[u] + w(u,v)) p[v] = u

Operazione riduzione del valore di un elemento

Tempo di esecuzione: DijkstraTempo di esecuzione: verifichiamo il tempo in relazione a differenti implementazioni della coda di priorità. Differenti implementazioni danno differenti costi per le operazioni sulla coda.

• Delete_Min quante volte viene eseguita?


• Delete_Min viene eseguita O(|V|) volte.


• Delete_Min viene eseguita O(|V|) volte.• Decrease_key viene eseguita O(|E|) volte.


• Delete_Min viene eseguita O(|V|) volte.• Decrease_key viene eseguita O(|E|) volte.•Tempo totale = |V| T + |E| TDelete_min Decrease_key

Tempo di esecuzione: Dijkstra

Decrease_keyCoda a priorità T T Total time

Array non ordinato

Heap binario

Delete_min

Tempo di esecuzione: verifichiamo il tempo in relazione a differenti implementazioni della coda di priorità. Differenti implementazioni danno differenti costi per le operazioni sulla coda.



O(|V|) O(1)


Array non ordinato

Heap binario

Delete_min




O(|V|2 )

O(log |V|) O(log |V|)

O(|V|) O(1)


Array non ordinato

Heap binario

Delete_min




O(E log |V|)

O(|V|) O(1)


Array non ordinato

Heap binario

Delete_min

O(|V|2 )

O(log |V|) O(log |V|)



Algoritmo di Dijkstra: correttezza

Teorema: Se eseguiamo l’algoritmo di Dijkstra su un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali non-negativi, e un vertice sor-gente s, allora, alla terminazione, d[u] = (s,u) per tutti i vertici u in V.


Lemma 4: Sia dato un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali. Sia s la sorgente e il grafo sia inizializzato con una chiamata a Inizializza(G,s). Allora, vale d[v] (s,v) per ogni vertice v di G e tale invariante viene mantenuto lungo ogni sequenza di operazioni di rilassamento. Inoltre, appena d[v] = (s,v), d[v] non cambia più.


Corollario 2: Sia dato un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali. Suppeoniamo che in G non esistano percorsi tra s e un vertice v. Allora dopo che grafo è stato inizializzato con Inizializza(G,s), vale d[v] = (s,v) e questa uguaglianza viene mantenuta lungo ogni sequenza di operazioni di rilassamento.


Lemma 5: Sia dato un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali. Sia s la sorgente e suv sia un percorso minimo per qualche u,vV. Il grafo sia inizializzato con una chiamata a Inizializza(G,s) e venga applicata una sequenza di operazioni di rilassamento che includa Relax(u,v,w).

Se, d[u] = (s,u) in qualunque momento prima della chiamata, allora vale d[v] = (s,v) sempre dopo la chiamata.


Dimostrazione: Dimostriamo che per ogni uV, quando u viene inserito in S, vale d[u] = (s,u). Procedamo per contraddizione.

Sia u il primo nodo per cui d[u] (s,u) quando viene inserito in S.

Considerando la sitazione all’inizio del while quando u viene inserito in S ottenendo la contraddizione d[u] = (s,u), esaminando il percorso minimo da s a u.

Sappiamo che: 1 u s poiché d[s] = 0 = (s,s) all’inizio del loop. 2 Ma allora deve pure valere anche S prima che u

sia inserito. 3 Ci deve essere un percorso da s a u altrimenti d[u] =

= (s,u) per il Corollario 2, e quindi contraddizione. 4 Se c’è un percorso, c’è anche un percorso minimo p.


Dimostrazione: Sia u il primo nodo per cui d[u] (s,u) quando viene inserito in S.

Sappiamo che: 1 u s 2 S 3 C’è un percorso da s a u. 4 C’è un percorso minimo p. p connette un nodo in S con un nodo (u) in V-S Sia y il primo in V-S di p e x il suo predecessore. p può essere scomposto in sxyu

yx

s u SV-S

p1

p2

p1 p2


Dimostrazione: Possiamo asserire che quando u è inserito in S, vale d[y] = (s,y).

Infatti sappiamo che u è il primo nodo per cui d[u] (s,u), quando viene inserito in S.

x appartiene ad S, quindi avevamo d[x] = (s,x) quando è stato inserito in S.

Ma l’algoritmo allora rilassa l’arco (x,y). Quindi per il Lemma 5, deve essere d[y] = (s,y), dopo la

chiamata a Relax(x,y,w).

yx

s u SV-S

p1

p2

Algoritmo di Dijkstra: correttezzaDimostrazione: Possiamo ora ottenere la nostra contrad-

dizione. Poiché y compare nel percorso minimo tra s e u e i pesi

(ed in particolare quelli in p2) sono tutti non-negativi, (s,y) (s,u)

e inoltre d[y] = (s,y) (s,u) d[u] (Lemma 4) Poiché sia u che y sono in V-S quando u viene estratto

dalla coda (linea 5), vale anche d[u] d[y]. Cioè d[y] = d[y], e quindi

d[y] = (s,y) = (s,u) = d[u]. (contraddizione!)

yx

s u SV-S

p1

p2

Lemma 4 ci garantisce inoltre che l’uguaglianza vale sempre dopo l’inserimento di u in S.

Algoritmo di Dijkstra: correttezza 2

Corollario: Se eseguiamo l’algoritmo di Dijkstra su un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali non-negativi, e un vertice sor-gente s, allora, alla terminazione il sottografo dei predecessori Gp corrisponde all’albero dei percorsi minimi con radice s.


Lemma 6: Sia dato un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali e sia s la sorgente.

Allora, dopo che il grafo è stato inizializzato con una chiamata a Inizializza(G,s), il sottografo dei predecessori Gp forma un albero con radice s, e qualunque sequenza di opra-zioni di rilassamento su G mantiene questa proprietà.


Dimostrazione: Per dimostrare il lemma è necessario dimostrare che:

• sempre Gp è un grafo aciclico; • sempre esiste almeno un percorso da s a vVp; • sempre esiste al più un percorso da s a vVp.

Dimostreremo solo la prima, per la dimostra-zione delle altre due vedere Cormen

Rilassamento e percorsi minimiDimostrazione: Dimostriamo che Gp è sempre un albero

(cioè Gp è un grafo aciclico). Appena eseguita l’inizializzazione la proprietà è ov-

viamente vera (unico nodo in Gp è s). Sia stata eseguita una sequenza di rilassamenti. Supponiamo che l’ultimo rilassamento abbia intro-dotto

un ciclo <v0,…,vk> (dove vk=v0). Possiamo assumere che sia stato il rilassamento dell’arco

(vk-1,vk) ad creare il ciclo. (perché?) - Tutti i nodi del ciclo sono raggigibili da s. Infatti, ogni nodo vi nel ciclo ha predecessore p[vi] non-

Nil quindi questi nodi ha valore finito di d[vi] quando p[vi] viene assegnato.

Per Lemma 4 ogni vi ha percorso minimo finito, quindi è raggiungibile da s.

Rilassamento e percorsi minimiDimostrazione: Supponiamo che l’ultimo rilassamento

abbia introdotto un ciclo <v0,…,vk> (dove vk=v0). Possiamo assumere che sia stato il rilassamento

dell’arco (vk-1,vk) ad creare il ciclo. (perché?) - Tutti i nodi del ciclo sono raggigibili da s.Appena prima del rilassamento di (vk-1,vk) abbiamo che

p[vi]=vi-1 per i=1,…,k-1 e l’ultimo assegnamento di d[vi] è stato d[vi] = d[vi-1] + w(vi-1,vi ). Se d[vi-1] è cambiato da allora, può solo essere diminuito.

Allora prima del rilassamento certamente valed[vi] d[vi-1] + w(vi-1,vi ) per i=1,…,k-1

Poiché p[vk] viene assegnato, prima del rilassamento deve valere d[vk] > d[vk-1] + w(vk-1,vk ).

Sommando le due disuguaglianse otteniamo

k

iiii

k

ii vvwvdvd

111

1

)],(][[][

Rilassamento e percorsi minimiDimostrazione: Supponiamo che l’ultimo rilassamento

abbia introdotto un ciclo <v0,…,vk> (dove vk=v0). Possiamo assumere che sia stato il rilassamento dell’arco

(vk-1,vk) ad creare il ciclo. (perché?) - Tutti i nodi del ciclo sono raggigibili da s.Appena prima del rilassamento di (vk-1,vk) abbiamo che

d[vi] d[vi-1] + w(vi-1,vi ) per i=1,…,k-1 d[vk] > d[vk-1] + w(vk-1,vk ).

Sommando le due disuguaglianze otteniamo

k

iiii

k

ii vvwvdvd

111

1

)],(][[][

k

iii

k

ii vvwvd

11

11 ),(][

k

ii

k

ii vdvd

11

1

][][

Perché ogni vertice del ciclo occorre una sola

volta in ogni sommatoria0),(

11

k

iii vvw

Contraddizione!


Lemma 7: Sia dato un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali. Sia s la sorgente e G non contenga cicli di peso negativo.

Il grafo sia inizializzato con una chiamata a Inizializza(G,s) e venga applicata una sequenza di operazioni di rilassamento che includa Relax(u,v,w) tale che d[v] = (s,v).

Allora il sottografo dei predecessori Gp è un albero di cammini minimi con radice s.


Dimostrazione: Per dimostrare il lemma è necessario dimostrare che:

• Vp contiene solo vertici raggiungibili da s; • Gp è un albero con radice s; • i percorsi in Gp sono percorsi minimi da s a

vVp.

Dimostreremo solo la terza, per la dimostrazione delle altre due vedere Cormen


Dimostreremo solo la terza: Sia p=<v0,…,vk> un percorso in Gp, dove v0=s e vk=v. Per i=1,…,k abbiamo le seguenti:

d[vi] = (s,vi)d[vi] d[vi-1] + w(vi-1,vi )

poiché se fosse minore, il predecessore di vi non in Gp potrebbe certo essere vi-1.

Ma allora possiamo concludere chew(vi-1,vi ) (s,vi) - (s,vi-1)


Dimostreremo solo la terza: Sia p=<v0,…,vk> un percorso in Gp, dove v0=s e vk=v.

Ma allora possiamo concludere chew(vi-1,vi ) (s,vi) - (s,vi-1)

Calcoliamo il peso del percorso p.

w(p ) = w(vi-1,vi ) i=1…k

(s,vi) - (s,vi-1) i=1…k

serie telescopica (s,vk) + (s,v0) (s,vk)

poiché (s,v0)=0. Ma (s,vk) è un limite per ogni percorso da s a vk. Quindi w(p) = (s,vk).

Algoritmo di Dijkstra: correttezza 2

Dimostrazione Corollario: Conseguenza imme-diata del Teorema di correttezza e del Lemma 7.

Esercizio

• Trovare il percorso minimo da b ad ogni altro vertice

c

42

1 4

3

4

4

ef

d

b

a5

11

0 4

2

3 5

8

c

42

1 4

3

4

4

ef

d

b

a5

11

Algoritmi e Strutture dati Mod B Grafi: Percorsi Minimi (parte I)

Documents

Transcript of Algoritmi e Strutture dati Mod B Grafi: Percorsi Minimi (parte I)