Cammini minimi da un sorgente Precondizioni: G = grafo orientato e pesato, w: E R funzione peso, s ...

Cammini minimi da un sorgente

Precondizioni:G = <V, E> grafo orientato e pesato, w: E R funzione peso, s VG non ha cicli di peso negativo raggiungibili da s

Dopo qualunque sequenza di RELAX sugli archi di G, eseguita dopo la INITIALIZE_SINGLE_SOURCE (G, s), si ha:

1. G è un albero di radice s.

2. Se vV, d[v] = (s, v), allora G è un albero di cammini minimi da s.

Se riusciamo ad individuare una strategia per effettuarele RELAX in modo da assicurare la condizione

d[v] = (s, v), vV

abbiamo risolto il problema di costruire un albero di cammini minimi da s.

Grazie alla proprietà 2 si può affermare che:

fare su tutti gli archi del grafoun numero di RELAX sufficiente ad assicurare la condizione.

Due strategie:


Algoritmo di Bellman-Ford

Due strategie:



Due strategie:

fare le RELAX in modo “guidato” su archi opportuni.



Due strategie:


Algoritmo di Dijkstra



fare le RELAX sugli archi uscenti da un vertice via via scelto “bene” e che non sia già stato preso in esame prima.




1^ approssimazione dell’algoritmo, dove S è l’insieme dei vertici già considerati:




1^ approssimazione dell’algoritmo, dove S è l’insieme dei vertici già considerati:

INITIALIZE_SINGLE_SOURCE (G, s)S while S V[G] do u vertice scelto “bene” S S {u} for ogni v ADJ[u] do

if v S then RELAX (u, v, w)

u vertice scelto “bene” ????????

Scriviamo un algoritmo greedy che effettua la scelta migliore in ogni istante e dimostreremo che tale scelta si rivela buona anche a lungo termine.



Scelta migliore a breve:un vertice la cui stima della distanza pesata è

minima tra tutte quelle dei vertici non ancora considerati.



Scelta migliore a breve:un vertice la cui stima della distanza pesata è

minima tra tutte quelle dei vertici non ancora considerati.

Riscriviamo l’algoritmo

INITIALIZE_SINGLE_SOURCE (G, s)S while S V[G] do u vertice con d minima tra tutti i

vertici non in S S S {u} for ogni v ADJ[u] do


INITIALIZE_SINGLE_SOURCE (G, s)S while S V[G] do u vertice con d minima tra tutti i

vertici non in S S S {u} for ogni v ADJ[u] do


Non sempre la scelta funziona!

A

B

D

C

E

25

23

-31

Ad esempio:

A

B

D

C

E

25

23

-31

Ad esempio:

Se il vertice sorgente è A, dopo le opportune RELAX, vengono scelti, nell’ordine:

A

B

D

C

E

25

23

-31

Ad esempio:


A (d[A] = 0, d[B] = d[C] = d[D] = d[E] = )

A

B

D

C

E

25

23

-31

Ad esempio:


A (d[A] = 0, d[B] = d[C] = d[D] = d[E] = )C (d[B] = 5, d[C] = 2, d[D] = 3, d[E] = )

A

B

D

C

E

25

23

-31

Ad esempio:


A (d[A] = 0, d[B] = d[C] = d[D] = d[E] = C (d[B] = 5, d[C] = 2, d[D] = 3, d[E] = )D (d[B] = 5, d[D] = 3, d[E] = )

A

B

D

C

E

25

23

-31

Ad esempio:


A (d[A] = 0, d[B] = d[C] = d[D] = d[E] = C (d[B] = 5, d[C] = 2, d[D] = 3, d[E] = )D (d[B] = 5, d[D] = 3, d[E] = )E (d[B] = 5, d[E] = 4)

A

B

D

C

E

25

23

-31

Ad esempio:


A (d[A] = 0, d[B] = d[C] = d[D] = d[E] = C (d[B] = 5, d[C] = 2, d[D] = 3, d[E] = )D (d[B] = 5, d[D] = 3, d[E] = )E (d[B] = 5, d[E] = 4)B (d[B] = 5)

A

B

D

C

E

25

23

-31

Ad esempio:

Ma (A, E) = 2, mentre d[E] = 4



A

B

D

C

E

25

23

-31

Ad esempio:

Ma (A, E) = 2, mentre d[E] = 4



La scelta funziona solo in assenza di archi di peso negativo

Riscriviamo l ‘algoritmo di Dijkstra aggiungendo come precondizione la richiesta che la funzione peso non assuma valori negativi.


{G = <V, E> grafo orientato e pesato and sV and w: E R+{0} funzione peso and G non ha cicli di peso negativo raggiungibili da s}


{G = <V, E> grafo orientato e pesato and sV and w: E R+{0} funzione peso}


INITIALIZE_SINGLE_SOURCE (G, s)S

while S V[G] do u vertice con d minima tra tutti i vertici non in S S S {u} for ogni v ADJ[u] do



Coda con priorità


INITIALIZE_SINGLE_SOURCE (G, s)S

while S V[G] do u vertice con d minima tra tutti i vertici non in S S S {u} for ogni v ADJ[u] do



INITIALIZE_SINGLE_SOURCE (G, s)S Q V[G] while S V[G] do (Q ) u extract_min (Q) S S {u} for ogni v ADJ[u] do

if v S (v Q) then RELAX (u, v, w)

INITIALIZE_SINGLE_SOURCE (G, s)S Q V[G] while S V[G] do (Q ) u extract_min (Q) S S {u} for ogni v ADJ[u] do

if v S (v Q) then RELAX (u, v, w)

Se è piu conveniente ricorda il nuovo camminoe aggiorna la stima della distanza

INITIALIZE_SINGLE_SOURCE(G, s) for ogni v V do d[v] [v] nil d[s] 0

Ricorda un altro algoritmo che conosciamo

L’algoritmo di PRIM

Ricorda un altro algoritmo che conosciamo

L’algoritmo di PRIM

riscriviamolo

INITIALIZE_ KEY(G, s)A Q V[G] while Q do u extract_min (Q) A A {([u], u)} for ogni v ADJ[u] do

if v Q then if key[v] > w(u,v)

then key[v] w(u,v) [v] u

INITIALIZE_ KEY(G, s) for ogni v V do key[v] [v] nil key[s] 0

INITIALIZE_ KEY(G, s)A Q V[G] while Q do u extract_min (Q) A A {u} for ogni v ADJ[u] do

if v Q then if key[v] > w(u,v)

then key[v] w(u,v) [v] u

INITIALIZE_ KEY(G, s) for ogni v V do key[v] [v] nil key[s] 0

Se è più conveniente ricorda il nuovo arcoe aggiorna la chiave

MST_Prim (G, s)INITIALIZE_ KEY(G, s)A Q V[G] while Q do u extract_min (Q) A A {([u], u)} for ogni v ADJ[u] do if v Q

then if key[v] > w(u,v)then key[v] w(u,v) [v] u

Dijkstra (G, w, s)INITIALIZE_SINGLE_SOURCE (G, s)S Q V[G] while Q do u extract_min (Q) S S {u} for ogni v ADJ[u] do

if v Q then RELAX (u, v, w)



Complessità: - coda realizzata con un array lineare O(V2)



Complessità: - coda realizzata con un array lineare O(V2)- coda realizzata con heap binario O((V+E)logV)

O(E logV)


RELAX (u, v, w)

N.B. Poichè per tutti i vertici t S: d[t] = (s, t) e d[t] non verrà più modificata da nessuna RELAX, diventa inutile condizionare la RELAX(u,v,w) al fatto che v Q.Tale semplificazione non è invece possibile nell’algoritmodi Prim.

Dobbiamo ancora dimostrare che l’algoritmo è corretto

Dijkstra (G, w, s)INITIALIZE_SINGLE_SOURCE (G, s)S Q V[G]

while Q do u extract_min (Q) S S {u} for ogni v ADJ[u] do

RELAX (u, v, w)


Dijkstra (G, w, s)INITIALIZE_SINGLE_SOURCE (G, s)S Q V[G] {t S: d[t] = (s, t) and S Q = V[G]}while Q do u extract_min (Q) S S {u} for ogni v ADJ[u] do

RELAX (u, v, w){t V[G] : d[t] = (s, t)}


Dijkstra (G, w, s)INITIALIZE_SINGLE_SOURCE (G, s)S Q V[G] {t S: d[t] = (s, t) and S Q = V[G]}while Q do u extract_min (Q) S S {u} for ogni v ADJ[u] do

RELAX (u, v, w){t V[G] : d[t] = (s, t)}{G è un albero di cammini minimi da s}



for ogni arco (u, v) E[G] doRELAX (u, v, w)

INITIALIZE_SINGLE_SOURCE (G, s)


for i = 1 to ? do



Si tratta di trovare un numero da sostituire al ?.


for i = 1 to ? do



Si tratta di trovare un numero da sostituire al ?.

Quante RELAX si dovranno fare per essere sicuri che le stime delle “distanze pesate” per ogni vertice siano diminuite abbastanza da raggiungere le distanze stesse?

Ricordiamo una proprietà delle RELAX

Se s u v e` un cammino minimo da s a v,allora:

{d[u] = (s, u)}RELAX(u, v, w){d[v] = (s, v)}


Se s u v e` un cammino minimo da s a v,allora:


Possiamo dedurre che, se vi e` un vertice t la cui distanza pesata da s e` data da un cammino di lunghezza 1, d[t] sara`uguale a (s, t) dopo la prima sequenza di RELAXsu tutti gli archi del grafo.


Se s u v è un cammino minimo da s a v,allora:


Possiamo dedurre che, se vi e` un vertice t la cui distanza pesata da s e` data da un cammino di lunghezza 1, d[t] sarà uguale a (s, t) dopo la prima sequenza di RELAXsu tutti gli archi del grafo.

Generalizzando: dopo n sequenze di RELAX su tutti gli archidel grafo i vertici t per cui esiste un cammino minimo da sdi lunghezza minore o uguale ad n hanno d[t] = (s, t).

Poichè, se nel grafo non ci sono cicli di peso negativo,i cammini minimi hanno al massimo lunghezza |V|-1,abbiamo trovato un valore per il ?

Bellman-Ford (G, w, s)INITIALIZE_SINGLE_SOURCE (G, s)

for i = 1 to |V|-1 do for ogni arco (u, v) E[G] do

RELAX (u, v, w)



RELAX (u, v, w)

Complessità: O(V . E)

Dimostriamo che l’algoritmo è corretto

{G = <V, E> grafo orientato e pesato and sV and w: E R funzione peso and non ci sono cicli di peso negativo raggiungibili da s}



RELAX (u, v, w)

{t V[G] : d[t] = (s, t)}

{G = <V, E> grafo orientato e pesato and sV and w: E R funzione peso and non ci sono cicli di peso negativo raggiungibili da s}



RELAX (u, v, w)

{t V[G] : d[t] = (s, t)}{G è un albero di cammini minimi da s}

Possiamo modificare l’algoritmo in modo da eliminarenella precondizione la richiesta che non vi siano cicli di peso negativo raggiungibili dal sorgente.


In assenza di cicli di peso negativo raggiungibili dal sorgente, alla fine dell’algoritmo G è un albero di cammini minimi da s, allora, per ogni vertice v raggiungibile da s, èvera la seguente uguaglianza:

d[v] = d[[v]] + w([v], v)


In assenza di cicli di peso negativo raggiungibili dal sorgente, alla fine dell’algoritmo G è un albero di cammini minimi da s, allora, per ogni vertice v raggiungibile da s, èvera la seguente uguaglianza:

d[v] = d[[v]] + w([v], v)

Tale uguaglianza sarà vera anche in presenza di cicli di peso negativo ?

Esempio: A

B

D

C

E

35

2- 4

- 31

0

Esempio: A

B

D

C

E

35

2- 4

- 31

0

Supponiamo di eseguire le RELAX sugli archi nel seguente ordine: <D,B>, <E,D>, <B,E>, <C,D>, <A,B>, <A,C>

Dopo la prima sequenza di RELAX si ha:

<D,B>, <E,D>, <B,E>, <C,D>, <A,B>, <A,C>

A

B

D

C

E

35

2- 4

- 31

0

5

3

A

B

D

C

E

35

2- 4

- 31

0

1

A

B

D

C

E

35

2- 4

- 31

0

5

3

<D,B>, <E,D>, <B,E>, <C,D>, <A,B>, <A,C>

A

B

D

C

E

35

2- 4

- 31

0

5

3

5

2

A

B

D

C

E

35

2- 4

- 31

0

5

3

<D,B>, <E,D>, <B,E>, <C,D>, <A,B>, <A,C>

2

A

B

D

C

E

35

2- 4

- 31

0

5

3

5

2

A

B

D

C

E

35

2- 4

- 31

0

5

3

<D,B>, <E,D>, <B,E>, <C,D>, <A,B>, <A,C>

A

B

D

C

E

35

2- 4

- 31

0

1

3

3

-2

3

2

A

B

D

C

E

35

2- 4

- 31

0

5

3

5

2

A

B

D

C

E

35

2- 4

- 31

0

5

3

<D,B>, <E,D>, <B,E>, <C,D>, <A,B>, <A,C>

A

B

D

C

E

35

2- 4

- 31

0

1

3

3

-2

3

2

A

B

D

C

E

35

2- 4

- 31

0

-1

3

-1

-4

4

A

B

D

C

E

35

2- 4

- 31

0

-1

2

-1

-4

[B] = Dd[B] = -1d[D] = -1d[B] > d[D] + w(D,B)

Bastano 4 cicli di RELAX perchè il grafo ha 5 vertici

A

B

D

C

E

35

2- 4

- 31

0

-1

2

-1

-4

[B] = Dd[B] = -1d[D] = -1d[B] > d[D] + w(D,B)

Bastano 4 cicli di RELAX perchè il grafo ha 5 vertici

Non e` casuale !Si ha sempre un arco del genere in presenza di cicli di peso negativo

Versione finale

{G = <V, E> grafo orientato e pesato and sV and w: E R funzione peso}



RELAX (u, v, w)for ogni arco (u, v) E[G] do if d[v] > d[u] + w(u, v)

then return “false”return “true”






{true non ci sono cicli di peso negativo raggiungibili da s}






{true non ci sono cicli di peso negativo raggiungibili da s}{true G è un albero di cammini minimi da s}

Cammini minimi da un sorgente Precondizioni: G = grafo orientato e pesato, w: E R funzione peso, s ...

Documents

Transcript of Cammini minimi da un sorgente Precondizioni: G = grafo orientato e pesato, w: E R funzione peso, s ...