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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 3

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 4

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)

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 5

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 ),()(

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 6

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 7

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)

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 8

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)

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 9

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 10

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 11

Esempio di cammino minimo

s

v4v3

v1 v2

t

16

4 10

12

9

3

2

9

1413

cammino minimo

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 12

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 13

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 14

Esempio

s

u

a

bc

7

-10

2

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 15

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?

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 16

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).

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 17

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 18

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'

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 19

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)

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 20

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 21

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}}

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 22

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 23

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)

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 24

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)

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 25

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).

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 26

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 27

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 28

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]

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 29

Come scegliamo gli archi?

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

Alcuni algoritmi rilassano ciascun arco più volte

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 30

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 31

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 32

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]

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 33

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 34

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

Resto delgrafo

S

frontiera

s

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 35

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)

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 36

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 37

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

12

9

6

51

3

8

s

I valori nei vertici indicano i valori di d

S

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 38

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

12

9

6

51

3

8

s

I valori nei vertici indicano i valori di d

Smin(9, 6+1) = 7

min(12, 6+3) = 9

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 39

Passo dell’algoritmo di Dijkstra

4

9

7

6

51

3

8s

I valori nei vertici indicano i valori di d

S

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 40

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 41

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 42

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'

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 43

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

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 44

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)

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 45

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)

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 46

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)

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 47

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)