Grafi (orientati): cammini minimi

(1)

F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)

Grafi (orientati): cammini minimi

Una presentazione alternativa (con ulteriori dettagli)

………..

Un algoritmo greedy per calcolare i

cammini minimi da un vertice sorgente in un grafo orientato e pesato, senza cicli di peso negativo raggiungibili dal sorgente.

Definiamo “distanza” di un vertice u da un vertice v: δ(v, u), in un grafo orientato e pesato, il peso di un cammino di peso minimo tra tutti i cammini da v a u.

δ(v, u) = min {W(p) | p cammino da v a u}

dove W(p) è la somma dei pesi degli archi che formano il cammino.

N.B. δ(v, u) è ben definita solo se nessun cammino tra v e u contiene un ciclo di peso negativo

Per costruire un algoritmo greedy, dobbiamo individuare l’ insieme di oggetti e definire per essi un grado di appetibilità.

Input: G = <V, E> grafo orientato e pesato,

w: E → R funzione peso, s ∈ V, G senza cicli di peso negativo raggiungibili da s

Output: ∀v ∈ V[G], l’attributo d[v] indica la “distanza” di v dal vertice sorgente: d[v] = δ(s, v)

Si può pensare ai vertici come agli oggetti tra i quali scegliere;

mantenendo per ogni vertice v, nell’attributo d[v] una stima (maggiore o uguale) della distanza di v da s.

Un vertice risulterà tanto più appetibile quanto minore è la stima della sua distanza dal sorgente stesso.

(2)

L’idea dell’algoritmo è la seguente:

Inizialmente si stima la distanza di ogni vertice da s uguale a ∞, tranne che per s stesso, di cui si conosce la distanza vera:

δ(s, s) = 0. Si definisce pertanto d[s] = 0

Si costruisce poi un albero, di radice s, in cui viene inserito un vertice per volta: il più appetibile.

L’albero è memorizzato implicitamente come l’insieme dei suoi archi < π[v], v>

Quando un vertice u è inserito nell’albero, si aggiornano le stime delle distanze dei vertici v ad esso adiacenti, in quanto potrebbe esitere un cammino da s a v, attraverso il vertice u, meno pesante del cammino da s a v considerato fino a quel momento.

Se il vertice sorgente è A, si ha inizialmente:

d[A] = 0, d[B] = d[C] = d[D] = d[E] = ∞ La strategia greedy sceglie percio’ il vertice A.

A B

D C

E 3 2

3 4 3

1

Da A sono raggiungibili con un arco i vertici B, C e D.

Si possono modificare pertanto le stime delle loro distanze da A.

d[B] = 3, d[C] = 2, d[D] = 4, mentre resta d[E] = ∞ Esempio

Scegliendo C si scopre il cammino A - C - D, ma d[D] non viene modificata in quanto il suo peso (5) è maggiore del peso del cammino A - D (di peso 4).

A B

D C

E 3 2

3 4 3

1

La scelta è ora tra i vertici B, D ed E, con d[B] = 3, d[D] = 4, d[E] = ∞, e la stategia greedy impone di scegliere B.

Si scopre così il cammino A - B - E e diventa d[E] = 6.

La scelta di D permette infine di ottenere d[E] = 5, ed E sarà

(3)

Usiamo il secondo schema greedy e scriviamo una prima approssimazione dell’algoritmo, dove S è l’insieme dei vertici già considerati:

Dijkstra(G, W, s) for ogni u∈ V do

d[u]← ∞ π[u] ← nil d[s] ← 0 S ← Φ

while S ≠ V[G] do

u ← “vertice con d minore tra quelli non ancora scelti”

S ← S ∪ {u}

for ogni v ∈ ADJ[u] do

if v ∉ S and d[v] > d[u] + W(u, v) then d[v] ← d[u] + W(u, v)

π[v] ← u

{valuta le appetibilità iniziali dei vertici}

{ci sono elementi da scegliere}

{scegli il vertice più appetibile}

{aggiorna le appetibilità dei vertici}

A B

D C

E 5 2

2 3 -3

1

Ad esempio:

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

Se il vertice sorgente è A, dopo le opportune modifiche alle stime delle distanze, vengono scelti, nell’ordine:

A (quando: d[A] = 0, d[B] = d[C] = d[D] = d[E] = ∞) C (quando: d[B] = 5, d[C] = 2, d[D] = 3, d[E] = ∞) D (quando: d[B] = 5, d[D] = 3, d[E] = ∞) E (quando: d[B] = 5, d[E] = 4) B (quando: d[B] = 5) Non sempre la strategia funziona!

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

Nell’esempio considerato è facile capire che il non corretto comportamento è dovuto alla presenza dell’arco <B, E>, il cui peso è negativo.

Allora, se la strategia greedy funziona, essa funziona solo in assenza di archi di peso negativo.

{G = <V, E> grafo orientato e pesato & s∈V &

& W: E → ℜ⁺∪{0}}

(4)

Dijkstra (G, W, s) for ogni u∈ V do

d[u]← ∞ π[u] ← nil d[s] ← 0 S ← Φ

while S ≠ V[G] do

S ← S ∪ {u}

if v ∉ S and d[v] > d[u] + W(u, v) then d[v] ← d[u] + W(u, v)

π[v] ← u

& W: E → ℜ⁺∪{0}}

Usiamo una coda con priorità

Dijkstra (G, W, s)

for ogni u∈ V do d[u] ← ∞ π[u] ← nil d[s] ← 0

S ← Φ

whileS ≠ V[G]do

S ← S ∪ {u}

if v ∉ S and d[v] > d[u] + W(u, v) then d[v] ← d[u] + W(u, v)

π[v] ← u Q ← V[G]

vertice con d minima Q ≠ Φ

v ∈ Q

Extract-min (Q)

& W: E → ℜ⁺∪{0}}

Ricorda un altro algoritmo che conosciamo

L’algoritmo di

PRIM

(5)

MST-Prim (G, W, r)

for ogni u ∈ Q do key[u] ← ∞ π[r] ← nil

key[r] ← 0 Q ← V[G]

whileQ ≠ Φdo u ←Extract-min(Q)

for ogni v ∈ Adj[u] do if v ∈ Qe W(u, v) < key[v]

then key[v] ← W(u, v) π[v] ← u

MST-Prim (G, W, r) for ogni u ∈ Q do key[u] ← ∞

π[u] ← nil key[r] ← 0

S ← Φ Q ← V[G]

whileQ ≠ Φdo u ←Extract-min(Q) S ← S ∪ {u}

MST-Prim (G, W, r) for ogni u ∈ Q do key[u] ← ∞

π[u] ← nil key[r] ← 0

S ← Φ Q ← V[G]

whileQ ≠ Φdo u ←Extract-min(Q) S ←S ∪ {u}

Dijkstra (G, W, s) for ogni u ∈ Q do d[u] ← ∞

π[u] ← nil d[r] ← 0

S ← Φ Q ← V[G]

while Q ≠ Φdo u ←Extract-min(Q) S ← S ∪ {u}

if v ∈ Qand d[u] + W(u, v) < d[v]

then d[v] ← d[u] + W(u, v) π[v] ← u

La complessità dell’algoritmo di Dijkstra è pertanto la stessa dell’algoritmo di Prim:

•coda realizzata con heap binario: O(E logV)

•coda realizzata con un heap di Fibonacci: O(E + V logV)

Dobbiamo ancora dimostrare che l’algoritmo è corretto

(6)

Dijkstra (G, W, s) for ogni u∈ V do d[u] ← ∞

π[u] ← nil d[s] ← 0

Q ← V[G]

S ← Φ while Q ≠ Φ do

u ← Extract-min (Q) S ← S ∪ {u}

if v ∈ Q and d[u] + W(u, v) < d[v]

then d[v] ← d[u] + W(u, v) π[v] ← u

& W: E → ℜ⁺∪{0}}

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

{∀t ∈ S: d[t] = δ(s, t) & S ∪ Q = V[G] & S ∩ Q = Φ}

Un sottocammino di un cammino minimo è minimo.

Proprietà 1.

Dimostazione.

Siano x e y due vertici qualunque in un cammino minimo p da u a v:

u x y v = p1p2p3

p =

W(p) = W(p1) + W(p2) + W(p3)

Se il sottocammino p2da x a y non fosse minimo, ne esisterebbe un altro p2’ di peso inferiore. In tal caso il cammino p’ = p1p2’ p3

sarebbe un cammino da u a v con W(p’) < W(p). Assurdo.

p1 p2 p3

Le seguenti asserzioni:

2.1 ∀v ∈ V[G]: v ∈ S ⇒ d[v] non viene modificata 2.2 ∀v ∈ Q: π[v] ≠ nil ⇒ π[v] ∈ S

2.3 ∀v ∈ V[G] - {s}: d[v] ≠ ∞ ⇔ π[v] ≠ nil

2.4 ∀v ∈ V[G] - {s}: d[v] ≠ ∞ ⇒ d[v] = d[π[v]] + W(π[v], v) sono invarianti del ciclo while.

Proprieta` 2.

u ← Extract-min (Q) S ← S ∪ {u}

ifv ∈ Q andd[u] + W(u, v) < d[v]

then d[v] ← d[u] + W(u, v) Dimostrazione. Ovvia esaminando il corpo del while.

(7)

Proprieta` 3.

Dimostrazione.

(⇒) Supponiamo l’asserzione vera e dimostriamo che,

se per il vertice u estratto dalla coda d[u] ≠ ∞, il cammino esiste.

Per ipotesi induttiva esiste un cammino da s a π[u]. Allora il cammino da s a π[u] piu` l’arco < π[u], u>

costituisce un cammino da s a u.

La seguente asserzione:

∀v ∈ S: d[v] ≠ ∞ ⇔ esiste un cammino da s a v in G e` invariante del ciclo while.

(⇐) Se u viene estratto da Q con d[u] = ∞, allora (*)tutti i vertici t in Q hanno d[t] = ∞. Supponiamo che tra s e u vi sia almeno un cammino:

s → v₁→ v₂→ . . . → v_k-1→ v_k≡ u.

Allora, tutti i vertici visul cammino devono avere d[vi] = ∞ (se vlavesse d[v_l] ≠ ∞, allora per (*)v_l∈ S, quindi anche v_i+1avrebbre d[v_i+1] ≠ ∞).

Ma questo è assurdo perché d[s] = 0.

Dimostriamo ora che il predicato

Per ipotesi induttiva ∀t ∈ S: d[t] = δ(s, t).

∀t ∈ S: d[t] = δ(s, t) & S ∪ Q = V[G] & S ∩ Q = Φ è un invariante del ciclo while.

•Il predicato è vero all’inizio poichè S è vuoto e Q = V[G].

•Supponiamo che sia vero quando l’albero è stato costruito parzialmente, e dimostriamo che per il nuovo vertice u estratto da Q, d[u] = δ(s, u).

s r

x

Sia u il vertice estratto da Q.

1.d[u] ≠ ∞

Sia π[u] = r (proprietà 2.3 ). Sappiamo allora (proprietà 2.2) che r ∈ S, cioè all’albero e che (proprietà 2.4) d[u] = d[r] + W(r, u).

Supponiamo che tra s e u esista un cammino di peso minore di d[u]; esso deve contenere un arco tra un vertice in S e uno in Q: <x, y>.

Si hanno due casi:

u s r

x y

(8)

W(s x y u) = W(s x y) + W(y u)

= d[y] + W(y u)

≥ d[y] (W(y u) ≥ 0perchè la funzione peso non può assumere valori negativi)

≥ d[u] ( perchè u è il vertice estratto da Q) d[u] = δ(s, u)

Questo cammino tra s e u può allora essere visto come la concatenazione di tre cammini

s x y u

Se s x y u è minimo, anche s x y è minimo (proprietà 1), quindi d[y], che è il suo peso, è uguale a δ(s, y).

∀t ∈ (S ^∪{u}): d[t] = δ(s, t)

&

(S ∪{u})∪ (Q - {u}) = V[G]

&

(S ^∪{u})∩ (Q - {u}) = Φ 2.d[u] = ∞

Se il vertice u viene estratto quando d[u] = ∞ allora non esiste nessun cammino tra s e u (proprietà 3), cioè d[u] = ∞ = δ(s, u)

Riepilogo

•

Algoritmo di Dijkstra per il calcolo di cammini minimi a sorgente singola, in un grafo orientato senza pesi negativi.

•

Grafi (orientati): cammini minimi