Grafi, cammini minimi in grafi pesati e orientati PDF

Indice 1. Definizione 2. Algoritmo di Dijkstra Grafi,...

Indice 1. Definizione 2. Algoritmo di Dijkstra Grafi, cammini minimi in grafi pesati e orientati 3. Correttezza dell’algoritmo di Dijkstra Corso di Algoritmi e strutture dati Corso di Laurea in Informatica Docenti: Ugo de’Liguoro, András Horváth Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 1/ 25 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 2/ 25 Sommario 1. Cammini minimi Obiettivo: I sia dato un un grafo orientato e pesato I capire il concetto “cammino minimo” I distanza di un vertice u da un vertice v : δ(v , u), il peso di un cammino di peso I sviluppare algoritmi per trovare cammini minimi da un singolo sorgente minimo tra tutti i cammini da v a u I δ(v , u) = min{W (p)|p è un cammino da v a u} dove W (p) è la somma dei pesi degli archi che formano il cammino I δ(v , u) è ben definito solo se nessun cammino da v ad u contiene un ciclo di peso negativo Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 3/ 25 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 4/ 25  2. Algoritmo per trovare cammini minimi da un dato nodo 2. L’idea dell’algoritmo I input: I inizialmente: s.d=0, ∀v ∈ V (G), v 6= s : v.d=∞ I grafo orientato e pesato I si costruisce un albero, di radice s, in cui viene inserito un vertice per volta I un nodo (sorgente) I l’albero è memorizzato implicitamente come l’insieme dei suoi archi (v.π, v ) I output: ∀v ∈ V (G) l’attributo v.d indica la distanza di v dal vertice sorgente I quando un vertice u è inserito nell albero, si aggiornano le stime delle I l’attributo v.d mantiene una stima (maggiore o uguale) della distanza di v da s distanze dei vertici v ad esso adiacenti, in quanto potrebbe esistere un cammino da s a v , attraverso il vertice u, meno pesante del cammino da s a v considerato fino a quel momento Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 5/ 25 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 6/ 25 2. Un esempio 2. Un esempio 3 A 2 3 A 2 C C B B 4 4 3 3 3 3 E D E D 1 1 I nodo di partenza: A I distanze: A.d=0, B.d=3, C.d=2, D.d=4, E.d=∞ I distanze: A.d=0, B.d=∞, C.d=∞, D.d=∞, E.d=∞ I da scegliere: C I da scegliere: A I nuove distanze: A.d=0, B.d=3, C.d=2, D.d=4, E.d=∞ I nuove distanze: A.d=0, B.d=3, C.d=2, D.d=4, E.d=∞ Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 7/ 25 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 8/ 25  2. Un esempio 2. Un esempio 3 A 2 3 A 2 C C B B 4 4 3 3 3 3 E D E D 1 1 I distanze: A.d=0, B.d=3, C.d=2, D.d=4, E.d=∞ I distanze: A.d=0, B.d=3, C.d=2, D.d=4, E.d=6 I da scegliere: B I da scegliere: D I nuove distanze: A.d=0, B.d=3, C.d=2, D.d=4, E.d=6 I nuove distanze: A.d=0, B.d=3, C.d=2, D.d=4, E.d=5 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 9/ 25 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 10/ 25 2. Un esempio 2. Un esempio 3 A 2 3 A 2 C C B B 4 4 3 3 3 3 E D E D 1 1 I distanze: A.d=0, B.d=3, C.d=2, D.d=4, E.d=5 I distanze: A.d=0, B.d=3, C.d=2, D.d=4, E.d=5 I da scegliere: E I nuove distanze: A.d=0, B.d=3, C.d=2, D.d=4, E.d=5 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 11/ 25 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 12/ 25  2. L’idea non funziona con pesi negativi 2. Algoritmo di Dijkstra 5 A 2 I applica l’idea vista in precedenza C B I funzione se tutti i pesi sono maggiori o uguali a 0 3 -3 2 E D 1 I partendo da A I A.d=0, B.d=∞, C.d=∞, D.d=∞, E.d=∞: → A I A.d=0, B.d=5, C.d=2, D.d=3, E.d=∞: → C I A.d=0, B.d=5, C.d=2, D.d=3, E.d=∞: → D I A.d=0, B.d=5, C.d=2, D.d=3, E.d=4: → E I A.d=0, B.d=5, C.d=2, D.d=3, E.d=4: → B Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 13/ 25 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 14/ 25 2. Algoritmo di Dijkstra 2. Complessità dell’algoritmo di Dijkstra Dijkstra(G, s) I l’algoritmo di Dijstra è molto simile a quello di Prim Q←V MST_Prim(G, s) for ∀v ∈ V do v.d← ∞, v.π ← nil Q←V s.d← 0 for ∀v ∈ V do v.d← ∞, v.π ← nil s.π← nil s.d← 0 while Q 6= ∅ do s.π← nil u ← togli nodo con d minimo da Q while Q 6= ∅ do for ∀v ∈ adj[u] do u ← togli nodo con d minimo da Q if v ∈ Q e u.d + W (u, v ) < v.d then for ∀v ∈ adj[u] do v.d ← u.d + W (u, v ) if v ∈ Q e——u.d +W (u, v ) < v.d then v.π ← u v.d ←——u.d +W (u, v ) v.π ← u I complessità dell’algoritmo di Dijkstra è uguale a quella di Prim Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 15/ 25 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 16/ 25  3. Correttezza dell’algoritmo 3. Correttezza dell’algoritmo I proprietà I: un sottocammino di un cammino minimo è minimo I proprietà II: invarianti del ciclo: I dimostrazione: 1. ∀v ∈ V (G) : v 6∈ Q ⇒ v.d non viene modificato I siano x e y due vertici qualunque in un cammino minimo p da u a v : 2. ∀v ∈ Q : v.π 6= nil ⇒ v.π 6∈ Q p = u p1 x p2 y p3 v = p1 p2 p3 3. ∀v ∈ V (G) − {s} : v.d 6= ∞ ⇔ v.π 6= nil I W (p) = W (p1 ) + W (p2 ) + W (p3 ) 4. ∀v ∈ V (G) − {s} : v.d 6= ∞ ⇒v.d =v.π.d + W (v.π, v ) I se il sottocammino p2 da x a y non fosse minimo, ne esisterebbe un altro p20 di I sono ovvii esaminando il ciclo dell’algoritmo peso inferiore I in tal caso il cammino p0 = p1 p20 p3 sarebbe un cammino da u a v con W (p0 ) < W (p) I allora p non è un cammino minimo, assurdo Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 17/ 25 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 18/ 25 3. Correttezza dell’algoritmo 3. Correttezza dell’algoritmo I proprietà III: invariante del ciclo: ∀v 6∈ Q : v.d 6= ∞ ⇔ esiste un cammino da s I proprietà III: invariante del ciclo: ∀v 6∈ Q :v.d 6= ∞ ⇔ esiste un cammino da s a v in G a v in G I dimostrazione: I dimostrazione: I ⇒: I ⇐: I inizializzazione: Q = V , non c’è nessun nodo che non fa parte di Q quindi è vero I se u viene estratto da Q con u.d=∞, allora tutti i vertici t ∈ Q hanno t.d=∞ I mantenimento: supponiamo che l’asserzione sia vera un certo punto I supponiamo che tra s e u vi sia almeno un cammino: dell’esecuzione per ogni nodo che non fa parte di Q s → v1 → v2 →...vk −1 → vk = u I dimostriamo che, se per il vertice u estratto dalla coda u.d 6= ∞, allora il cammino I allora, tutti i vertici vi sul cammino devono avere vi.d=∞ esiste I (perché se vl avesse vl.d6= ∞, allora vl 6∈ Q, quindi anche vl+1 avrebbe vl+1.d6= ∞) I per ipotesi esiste un cammino da s a u.π I ma questo è assurdo perchè s.d=0 I allora il cammino da s a u.π più l’arco (u.π, u) costituisce un cammino da s a u Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 19/ 25 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 20/ 25  3. Correttezza dell’algoritmo 3. Correttezza dell’algoritmo I invariante principale del ciclo: ∀t 6∈ Q :t.d = δ(s, t) I dimostrazione: s I il predicato è vero all’inizio poichè Q = V (G) I supponiamo che sia vero quando l’albero è stato costruito parzialmente r I dimostriamo che per il nuovo vertice u estratto da Q, il predicato verrà mantenuto x u y Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 21/ 25 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 22/ 25 3. Correttezza dell’algoritmo 3. Correttezza dell’algoritmo s I caso I: u.d 6= ∞ I caso I: u.d 6= ∞ I cammino tra s e u può allora essere visto come la s I sia u.π = r (proprietà 2.3) r concatenazione di tre cammini: s x →y u I sappiamo allora (proprietà 2.2) che r 6∈ Q I se s x →y u è minimo, allora anche I u.d = r.d + W (r , u) (proprietà 2.4) r s x → y è minimo (proprietà 1) I supponiamo che tra s e u esista un cammino di peso x I quindi y.d = δ(s, y ) minore di u.d u I W (s x →y u) = W (s x → y ) +W (y u) x I esso deve contenere un arco tra un vertice in y I W (s x →y u) = y.d + W (y u) u V (G) − Q e uno in Q: (x, y ) I W (s x →y u) ≥ y.d y I W (s x →y u) ≥ y.d ≥ u.d (u era astratto da Q) I =⇒ u.d = δ(s, u) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 23/ 25 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 24/ 25  3. Correttezza dell’algoritmo I caso II: u.d = ∞ I se il vertice u viene estratto quando u.d = ∞, allora non esiste nessun cammino tra s e u (proprietà 3) I cioè u.d = ∞ = δ(s, u) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 25/ 25