Cammini minimi
con sorgente
singola
1/31
Cammini minimi
con sorgente
singola
2/31
Cammini minimi con sorgente singola
Dato un grafo (orientato o non orientato) G = (V,E) con
funzione di peso w: E  R e dato un particolare vertice
sV, il problema chiede di trovare per ogni vertice vV il
cammino di peso minimo da s a v.
Altri casi:
•trovare il cammino minimo fra una coppia di vertici u e v.
•trovare i cammini minimi fra tutte le coppie di vertici.
Ipotesi: nel grafo non esistono cicli di peso negativo.
3/31
Rappresentazione
I cammini vengono rappresentati analogamente agli alberi BFS.
Per ogni vertice vV si mantiene un predecessore (v).
I valori di  inducono un sottografo dei predecessori G=(V,E).
G è un albero di cammini minimi, cioè:
• V è l’insieme dei vertici raggiungibili da s in G.
• G forma un albero con radice in S
• per ogni vV, l’unico cammino semplice da s a v in G è un
cammino minimo da s a v in G.
4/31
Algoritmo di Dijkstra:
InitializeSingleSource
Algoritmo basato su un rilassamento: in d[v] si tiene un limite
superiore al costo del cammino minimo da s a v (stima di cammino
minimo).
p[v]: predecessore del vertice v.
Inizializzazione delle strutture:
Initialize-Single-Source(G, s)
1 foreach v  V[G] do
2
d[v] = 
3
p[v] = nil
4 d[s] = 0
5/31
Algoritmo di Dijkstra: Relax
Rilassamento di un arco (u,v): verifica se è possibile
migliorare il cammino minimo verso v passante per u
trovato fino a quel momento.
Se si, si aggiornano d[v] e p[v].
Relax(u, v,
1 if d[v] >
2 then d[v]
3
p[v]
w)
d[u] + w(u,v)
= d[u] + w(u,v)
= u
6/31
Algoritmo di Dijkstra
Mantiene un insieme S che contiene i vertici v il cui peso
del cammino minimo da s, (s,v), è già stato determinato.
Dijkstra(G,w,s)
1. Initialize-Single-Source(G,s)
2. S = 
3. Q = V[G]
4. while Q  0 do
5.
u = Extract-Min(Q)
6.
S = S  {u}
7.
foreach v  Adj[u] do
8.
Relax(u,v,w)
7/31
Algoritmo di Dijkstra

10
2
0
5
1

9
3
4
6
7

2

8/31
Algoritmo di Dijkstra: esempio
10
10
2
0
5
1

9
3
4
6
7
5
2

9/31
Algoritmo di Dijkstra: esempio
8
10
2
0
5
1
14
9
3
4
6
7
5
2
7
10/31
Algoritmo di Dijkstra: esempio
8
10
2
0
5
1
13
9
3
4
6
7
5
2
7
11/31
Algoritmo di Dijkstra: esempio
8
10
2
0
5
1
9
9
3
4
6
7
5
2
7
12/31
Algoritmo di Dijkstra: esempio
8
10
2
0
5
1
9
9
3
4
6
7
5
2
7
13/31
Algoritmo di Dijkstra: correttezza
Teorema:
Se si esegue l’algoritmo di Dijkstra su di un
grafo orientato e pesato G=(V,E) con
funzione di peso non negativa W e sorgente s,
allora al termine vale d[u]=(s,u) per ogni
vertice uV.
14/31
Algoritmo di Dijkstra: complessità
InitializeSingleSource
TI(V,E) = O(V)
Relax
TR(V,E) = O(1)
Dijkstra (coda Q=V-S come array)
T(V,E) = TI(V,E) + O(V2) + E TR(V,E) =
= O(V) + O(V2) + E O(1) = O(V2+E) = O(V2)
15/31
Algoritmo di Bellman-Ford
Possibili archi con peso negativo.
Restituisce un booleano che dice se esiste un ciclo di peso negativo
(nessuna soluzione) oppure produce l’albero dei cammini minimi.
BellmanFord(G,w,s)
1 Initialize-Single-Source(G,s)
2 for i = 1 to |V[G]1| do
3
for (u,v) E[G] do
4
Relax(u,v,w)
5 for (u,v)  E[G] do
6
if d[v] > d[u] + w(u,v)
7
then return false
8 return true
16/31
Algoritmo di Bellman-Ford: esempio
-2
6

-3
8
0
7
2


5
9
-4
7

17/31
Algoritmo di Bellman-Ford: esempio
6
6
-2
-3
8
0
7
2
7

5
9
-4
7

18/31
Algoritmo di Bellman-Ford: esempio
6
6
-2
-3
8
0
7
2
7
4
5
9
-4
7
2
19/31
Algoritmo di Bellman-Ford: esempio
6
2
-2
-3
8
0
7
2
7
4
5
9
-4
7
2
20/31
Algoritmo di Bellman-Ford: esempio
6
2
-2
-3
8
0
7
2
7
4
5
9
-4
7
-2
TRUE
21/31
Algoritmo di Bellman-Ford: correttezza
Teorema
Si esegua Bellman-Ford su un grafo orientato
e pesato G=(V,E) con sorgente s e funzione di
peso w: ER. Se G non contiene cicli di peso
negativo l’algoritmo restituisce TRUE e si ha
che d[v]=(s,v) per tutti i vertici vV e che il
sottografo dei predecessori è un albero di
cammini minimi radicato in s. Se G ha un ciclo
di peso negativo, l’algoritmo restituisce
FALSE.
22/31
Algoritmo di Bellman-Ford: complessità
InitializeSingleSource
TI(V,E) = O(V)
Relax
TR(V,E) = O(1)
BellmanFord
T(V,E) = TI(V,E) + V E TR(V,E) + E =
= O(V) + V E O(1) + E =
= O(V E)
23/31
Cammini minimi in DAG: SSSP-DAG
Rlassando gli archi di un grafo pesato G=(V,E) secondo un
ordine topologico, si possono calcolare i cammini minimi da
una singola sorgente in tempo O(V+E).
DAG-Shortest-Path(G,w,s)
1 ordina topologicamente i vertici di G
2 Initialize-Single-Source(G,s)
3 foreach vertice u nell’ordine topologico do
4
foreach vertice v  Adj[u] do
5
Relax(u,v,w)
24/31
Cammini minimi in DAG: esempio
6

5
0
3
2

1
7

-1

-2

4
2
25/31
Cammini minimi in DAG: esempio
6

5
0
3
2

1
7

-1

-2

4
2
26/31
Cammini minimi in DAG: esempio
6

5
0
3
2
2
1
7
6
-1

-2

4
2
27/31
Cammini minimi in DAG: esempio
6

5
0
3
2
2
1
7
6
-1
6
-2
4
4
2
28/31
Cammini minimi in DAG: esempio
6

5
0
3
2
2
1
7
6
-1
5
-2
4
4
2
29/31
Cammini minimi in DAG: esempio
6

5
0
3
2
2
1
7
6
-1
5
-2
3
4
2
30/31
Cammini minimi in DAG: esempio
6

5
0
3
2
2
1
7
6
-1
5
-2
3
4
2
31/31
Cammini minimi in DAG: complessità
T(V,E) = (V + E) + (V) + E (1) = (V + E)
32/31