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)