F04 Cammini Minimi - UNISAcaprera.dia.unisa.it/LASD/SLIDE/F04CamminiMinimi.pdf · Prof. Carlo...

Cammini Minimi

Algoritmo di Dijkstra

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 2

Cammino in un grafo

Dato un grafo G=(V,E), un Cammino(Percorso) in G è un insieme di vertici v1, v2,….., vk tali che – (vi, vi+1) ∈E – v1 ≠ v2 ≠ v3 … ≠ vk

In un grafo orientato si farà riferimento a cammini diretti


Connettività in grafi non orientati

Due vertici u,v sono connessi in un grafo non orientato se esiste un cammino che collega u e v

Un grafo è connesso se per ogni coppia di vertici u e v, u e v sono connessi


Connettività in grafi orientati

Due vertici u e v sono connessi in un grafo orientato se esiste un cammino diretto che collega u a v Un grafo diretto è fortemente connesso se per ogni coppia (u,v), esiste un cammino da u a v e da v ad uUn grafo è debolmente connesso se per ogni coppia (u,v), esiste un cammino da u a v (o viceversa)


Costo di un cammino

Sia G = (V,E) un grafo orientato ai cui archi è associato un costo W(u,v).Il costo di un cammino p = (v0,v1,...,vk) è la somma dei costi degli archi che lo costituiscono

∑ = −=k

i ii vvWpW1 1 ),()(


Costo di un cammino minimoIl costo minimo del cammino da un vertice u ad un vertice v è definito nel seguente modo:

Un cammino minimo da u a v è un cammino p da u a v di costo W(p) = δ(u,v)

min {W(p)} se esistono cammini p da u a v

δ(u,v) = ∞ altrimenti


Varie versioni del problema – 1Nel problema dei cammini minimi viene richiesto di calcolare i cammini minimi in un grafo orientatoVi sono quattro versioni del problema:– Cammini minimi da un'unica sorgente a

tutti gli altri vertici (Single Source Shortest Paths)

– Cammini minimi da ogni vertice ad un'unica destinazione (Single Destination Shortest Paths)


Varie versioni del problema – 2

Cammini minimi da un'unica sorgente ad un’unica destinazione (Single-PairShortest Path)

Cammini minimi da ogni vertice ad ogni altro vertice (All Pairs Shortest Paths)


Risoluzione dei vari problemiNoi risolveremo la prima istanzaLa seconda istanza si risolve simmetricamente La terza si può risolvere usando la soluzione della prima – Non si conosce ancora un algoritmo che risolva la

terza istanza in tempo asintoticamente migliore della prima

La quarta istanza si può risolvere usando la soluzione della prima per ogni vertice del grafo – In genere si può fare di meglio


Esempio di applicazioneSi supponga di voler determinare il percorso più breve (in termini di chilometri) che collega due luoghi A e BSe si modella la carta stradale su cui compaiono A e B come un grafo in cui:– I vertici sono gli incroci– Gli archi sono i tratti di strada tra incroci successivi– I pesi degli archi sono le distanze in chilometri di ciascun

arcoIl problema si riconduce a quello dell'identificazione del cammino minimo dal vertice corrispondente ad A al vertice corrispondente a B


Esempio di cammino minimo

s

v4v3

v1 v2

t

16

4 10

12

9

3

2

9

1413

cammino minimo


Note

Nel caso di grafi non pesati, l'identificazione dell'albero dei cammini minimi può essere eseguita tramite la procedura di visita in ampiezza

Non vogliamo calcolare solo il costo dei cammini minimi, ma anche i cammini minimi stessi


Archi di costo negativoNel grafo orientato ci potrebbero essere anche archi di costo negativoQuesti archi potrebbero creare dei problemi nell’individuazione dei cammini minimi– Vi potrebbero essere dei cicli di costo negativo

raggiungibili da s– Se un vertice u è raggiungibile da s tramite un

cammino p che passa per un vertice appartenente ad un ciclo di costo negativo, allora esisteranno cammini da s a u di costo sempre minore

• costo minimo di cammino δ(s,u) non è definito


Esempio

s

u

a

bc

7

-10

2

Nel caso di cicli negativi si pone δ(s,u)= ∞−


Archi di costo positivo

Supporremo che il grafo orientato avrà solo archi di costo positivoIn questo caso il cammino di lunghezza minima non contiene cicli – Dimostrazione?


Teorema: Sottostruttura ottimale

Se p è un cammino minimo da u a v,allora ogni sotto-cammino di p è ancheun cammino minimoIn altre parole:– Se il cammino p = (v0,v1,...,vk) è minimo

allora sono minimi anche tutti i sottocammini pij = (vi,...,vj).


DimostrazioneSe esistesse un cammino q da vi a vj di costo minore di pij allora sostituendo nel cammino p il sottocammino pij con il cammino q si otterrebbe un cammino da v0 a vk di costo minore di p– Impossibile se p è minimo

v0 vi vj vk

q

X


Scomposizione dei costi di un cammino minimo

Se p è un cammino minimo da s ad un vertice v ed u è il vertice che precede v nel cammino allora

δ(s,v) = δ(s,u) + W(u,v)Dimostrazione: – Dipende dalla sottostruttura ottima:

δ(s,v) = W(p) = δ(s,u) + W(u,v)s

uv

p'


Limite superiore per i costi di cammino minimo

Per ogni arco (u,v) vale la disuguaglianza:δ(s,v) ≤ δ(s,u) + W(u,v)

Dimostrazione– Se u non è raggiungibile da s allora δ(s,u) = ∞ e

δ(s,v) ≤ ∞ + W(u,v) banalmente– Se u è raggiungibile da s allora δ(s,u) + W(u,v) è il

costo di un cammino da s a v ed è quindi maggiore o uguale di δ(s,v)


Rappresentazione dei cammini minimi – 1

In genere ci interessa calcolare non solo i costi dei cammini minimi dalla sorgente s ad ogni vertice del grafo ma anche i cammini minimi stessi

Dato un vertice u con π[u] indichiamo il predecessore di u nel cammino da s a u


Rappresentazione dei cammini minimi – 2

G=(V,E) s ∈ V s = sorgente Definiamo Gπ =(Vπ,Eπ) il sottografo predecessore di G con

– Vπ={v ∈ V: π[v] ≠ NIL} ∪ {s}

– Eπ ={(π[v],v) ∈ E : v ∈ Vπ-{s}}


Sottografo predecessore

Un sottografo predecessore Gπ è uno shortest-paths tree per G se– Vπ è costituito da tutti i vertici di G raggiungibili

da s– Gπ forma un albero con radice s– il cammino semplice da s a v in Gπ coincide

con il cammino minimo da s a v in G


Tecnica del rilassamento

L’algoritmo che studieremo per risolvere il problema dei cammini minimi usa la tecnica del rilassamento – Dettagli a breve

Ad ogni vertice v del grafo associamo un campo d[v] che rappresenta una stima di δ(s,v)– Durante l’esecuzione dell’algoritmo è un limite

superiore per δ(s,v) [d[v] ≥ δ(s,v)]; mentre alla fine sarà uguale a δ(s,v)


Idea dell’algoritmo – 1

I valori d[v] e π[v] vengono aggiornati mediante la cosiddetta tecnica del rilassamento degli archi – quando viene rilassato l’arco (u,v) si verifica

se è possibile ottenere un cammino più breve di quello di costo d[v] attraversando l’arco (u,v)


Rilassamento di un arco

Il rilassamento rispetto ad un arco (u,v) consiste nel controllare se è possibile migliorare il cammino finora trovato per v aggiungendo al cammino trovato per ul’arco (u,v).


Idea dell’algoritmo – 2Rilassamento di un arco

RELAX(u, v, w)if d[u] + w(u, v) < d[v] thend[v] ← d[u] + w(u, v)π[v] ← u //predecessore di u sul cammino di costo d[v]

InizializzazioneINITIALIZE-SINGLE-SOURCE(G, s)

for each vertex v ∈ V[G]d[v] ← ∞π[v] ← nil

d[s] ← 0


Effetto del rilassamento

Dopo aver eseguito RELAX(u, v, w) vale la disuguaglianza

d[v] ≤ d[u] + W(u,v)

Se d[v] > d[u] + W(u,v) prima del rilassamento, allora viene posto d[v] = d[u] + W(u,v)

Se d[v] ≤ d[u] + W(u,v) prima del rilassamento, allora non viene fatto nulla


Idea dell’algoritmo – 3

Si esegue INITIALIZE-SINGLE-SOURCE(G, s)

Ogni arco (u,v) viene rilassato eseguendo RELAX(u, v , w) L’algoritmo termina quando i valori di d coincidono con i pesi dei cammini minimi– Si noti che se ad un certo punto d[u]=δ(s,u),

allora nessuna successiva invocazione di RELAX può modificare d[u]


Come scegliamo gli archi?

L’ordine in cui gli archi vengono rilassati dipende dal tipo di algoritmo

Alcuni algoritmi rilassano ciascun arco più volte


Nota

Si può provare che qualsiasi algoritmo che esegua l’inizializzazione ed una sequenza di rilassamenti per cui alla fine d[v] = δ(s,v) per ogni vertice vcalcola correttamente i cammini minimi


Algoritmi per SSSP

Vi sono due algoritmi classici di questo tipo, uno dovuto a Dijkstra ed uno dovuto a Bellman-Ford

L’algoritmo di Dijkstra richiede che i pesi degli archi non siano negativi mentre quello di Bellman-Ford funziona anche nel caso generale


Algoritmo di Dijkstra – 1

Input: grafo direzionato G=(V,E) con archi di peso maggiore o uguale a 0 un vertice s che rappresenta la sorgenteL’algoritmo mantiene– Per ogni u ∈ V, i valori d[u] e π[u] – S: insieme di vertici per cui è stato già determinato

un cammino minimo• Per ogni u∈S si ha d[u]=δ(s,u)

– Q: coda a priorità che contiene i vertici che non sono in S

• Per ogni u ∈ Q, la chiave che determina la priorità di u èd[u]


Algoritmo di Dijkstra – 2I vertici adiacenti a quelli in S formano una frontiera tra i vertici per cui si conosce un cammino minimo e tutti gli altri verticiOgni volta viene inserito in S il vertice della frontiera che ha il valore di d più piccolo (scelta greedy) e vengono rilassati tutti gli archi uscenti da esso – Ogni arco è rilassato esattamente una volta

Output:– π: sottografo predecessore,– d: pesi dei cammini minimi da s a tutti gli altri

vertici


Algoritmo di Dijkstra – 3Per ogni vertice u di S è già noto il cammino minimo da s ad u

Resto delgrafo

S

frontiera

s


Pseudocodice dell’algoritmo di Dijkstra

DIJKSTRA(G,w,s)1 INITIALIZE-SINGLE-SOURCE(G, s)2 S ← ∅3 Q ← V[G]4 while Q ≠ ∅5 do u← Extract-Min(Q)6 S ←S∪{u}7 for each v ∈ Adj[u]8 do RELAX(u,v,w)


Passo dell’algoritmo di Dijkstra

Per ogni nodo u della frontiera, d[u] contiene la lunghezza di un percorso passante solo per vertici in S

0

4

∞

∞

6

51

3

8

min(4+5, ∞) = 9

s

I valori nei vertici indicano i valori di d

S

min(4+8, ∞) = 12




0

4

12

9

6

51

3

8

s


S




0

4

12

9

6

51

3

8

s


Smin(9, 6+1) = 7

min(12, 6+3) = 9



4

9

7

6

51

3

8s


S



Correttezza dell’algoritmo

Sia u il vertice della frontiera con il più piccolo valore di d. Un qualsiasi cammino minimo da s ad u attraversa solovertici in S

Su

s


Correttezza dell’algoritmo di Dijkstra – 1

Sia u il vertice della frontiera con il più piccolo valore di d. Qualsiasi cammino da s ad u che attraversa qualche vertice in V-S ha lunghezza maggiore di d[u] in quanto deve passare attraverso qualche altro vertice x della frontiera con d[x]≥d[u] per poi raggiungere u

Su

sx


Correttezza dell’algoritmo di Dijkstra – 2

Sia un percorso minimo da s a v. Se prima della chiamata a RELAX(u,v,w) si ha d[u]= δ(s,u), allora dopo la chiamata si ha d[v]= δ(s,v).Dimostrazione

d[v]≤d[u]+w(u,v) Per effetto di RELAX(u,v,w)

= δ(s,u)+w(u,v)= δ(s,v) Per la sottostruttura ottimale

s uvp'


Correttezza dell’algoritmo di Dijkstra – 3Teorema: Quando u viene inserito in S si ha d[u] = δ(s,u).

Idea della dimostrazione: Da quanto illustrato nelle due slide precedenti segue che esiste un cammino minimo tra s ed u che attraversa solo vertici di S:

Siccome d[z] = δ(s,z), allora il risultato della slide precedente implica che dopo RELAX(z,u,w) (eseguita quando z viene aggiunto ad S) risulta d[u] = δ(s,u) (e π[u] = z).

s z uS


Complessità dell’algoritmo di Dijkstra

Il tempo di esecuzione dipende da come èimplementata la coda a priorità QPer l’analisi considereremo tre diverseimplementazioni di Q– Mediante un array– Mediante binary heap– Mediante Fibonacci Heap

INITIALIZE-SINGLE-SOURCE(G, s) richiede tempo O(V)


Q implementata con arrayInizializzazione di Q– Tempo O(V) per inserire i vertici nell’array

Analisi del ciclo di while – V operazioni Extract-Min (linea 5)

• Ciascuna richiede tempo O(V) in quanto occorre cercare il minimo

– V aggiornamenti di S• Ciascuna richiede tempo costante

– Un totale di O(E) iterazioni del ciclo di for (linee 4-8) inquanto la lista di adiacenza di ciascun vertice u viene scandita esattamente una volta (quando u è inserito in S)

• RELAX(u,v,w) sulla linea 8 richiede tempo costante

Tempo totale: O(V2 + E )=O(V2)


Q implementata con binary heapInizializzazione di Q– effettuata mediante una Build-Heap che costruisce un heap con

V elementi in tempo O(V)

Analisi del ciclo di while – V operazioni Extract-Min - Ciascuna richiede tempo O(log V)– V aggiornamenti di S - Ciascuna richiede tempo costante– Un totale di O(E) iterazioni del ciclo di for (linee 4-8) in

quanto la lista di adiacenza di ciascun vertice u viene scandita esattamente una volta (quando u è inserito in S)

• RELAX(u,v,w) sulla linea 8 :– L’aggiornamento di d[v] è effettuata eseguendo DECREASE-

KEY(Q,v,d[u]+w(u,v)) che richiede tempo O(log V)– L’aggiornamento di π[v] richiede tempo costante

Tempo totale: O(Vlog V + E log V)


Q implementata con Fibonacci heapInizializzazione di Q – effettuata mediante V Make-Heap e V-1 Union in tempo O(V)

Analisi del ciclo di while– V operazioni Extract-Min - Ciascuna richiede tempo O(log V)– V aggiornamenti di S- Ciascuna richiede tempo costante– Un totale di O(E) iterazioni del ciclo di for (linee 4-8) in

quanto la lista di adiacenza di ciascun vertice u viene scandita esattamente una volta (quando u è inserito in S)

• RELAX(u,v,w) sulla linea 8 :– L’aggiornamento di d[v] è effettuata eseguendo DECREASE-

KEY(Q,v,d[u]+w(u,v)) che richiede tempo ammortizzato O(1)– L’aggiornamento di π[v] richiede tempo costante

Tempo totale: O(Vlog V + E)

F04 Cammini Minimi - UNISAcaprera.dia.unisa.it/LASD/SLIDE/F04CamminiMinimi.pdf · Prof. Carlo...

Documents

Transcript of F04 Cammini Minimi - UNISAcaprera.dia.unisa.it/LASD/SLIDE/F04CamminiMinimi.pdf · Prof. Carlo...