Post on 01-May-2015
transcript
1/31
Cammini minimi con sorgente singola
2/31
Cammini minimi con sorgente singola
3/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 sV, il problema chiede di trovare per ogni vertice vV 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.
4/31
Rappresentazione
I cammini vengono rappresentati analogamente agli alberi BFS.
Per ogni vertice vV 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 vV, l’unico cammino semplice da s a v in G è un
cammino minimo da s a v in G.
5/31
Algoritmo di Dijkstra: InitializeSingleSource
Initialize-Single-Source(G, s)1 foreach v V[G] do2 d[v] = 3 p[v] = nil4 d[s] = 0
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:
6/31
Algoritmo di Dijkstra: Relax
Relax(u, v, w)1 if d[v] > d[u] + w(u,v)2 then d[v] = d[u] + w(u,v)3 p[v] = u
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].
7/31
Algoritmo di Dijkstra
Dijkstra(G,w,s)1. Initialize-Single-Source(G,s)2. S = 3. Q = V[G]4. while Q 0 do5. u = Extract-Min(Q)6. S = S {u}7. foreach v Adj[u] do8. Relax(u,v,w)
Mantiene un insieme S che contiene i vertici v il cui peso del cammino minimo da s, (s,v), è già stato determinato.
8/31
Algoritmo di Dijkstra
10
1
5
2
649
7
2 3
0
9/31
Algoritmo di Dijkstra: esempio
1010
1
5
2
649
7
2 3
5
0
10/31
Algoritmo di Dijkstra: esempio
810
1
5
2
649
7
2 3
7
14
0
5
11/31
Algoritmo di Dijkstra: esempio
810
1
5
2
649
7
2 3
13
0
5 7
12/31
Algoritmo di Dijkstra: esempio
10
1
5
2
649
7
2 3
9
0
5 7
8
13/31
Algoritmo di Dijkstra: esempio
10
1
5
2
649
7
2 30
5 7
8 9
14/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 uV.
15/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)
16/31
Algoritmo di Bellman-Ford
BellmanFord(G,w,s)1 Initialize-Single-Source(G,s)2 for i = 1 to |V[G]1| do3 for (u,v) E[G] do4 Relax(u,v,w)5 for (u,v) E[G] do6 if d[v] > d[u] + w(u,v)7 then return false8 return true
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.
17/31
Algoritmo di Bellman-Ford: esempio
0
6
7
7-3
2
8-4
9
5-2
18/31
Algoritmo di Bellman-Ford: esempio
0
66
7
7-3
2
8-4
9
5-2
7
19/31
Algoritmo di Bellman-Ford: esempio
0
66
7
7-3
2
8-4
9
5-2
27
4
20/31
Algoritmo di Bellman-Ford: esempio
0
26
7
7-3
2
8-4
9
5-2
27
4
21/31
Algoritmo di Bellman-Ford: esempio
0
26
7
7-3
2
8-4
9
5-2
-27
4
TRUE
22/31
Algoritmo di Bellman-Ford: correttezza
TeoremaSi esegua Bellman-Ford su un grafo orientato e pesato G=(V,E) con sorgente s e funzione di peso w: ER. Se G non contiene cicli di peso negativo l’algoritmo restituisce TRUE e si ha che d[v]=(s,v) per tutti i vertici vV 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.
23/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)
24/31
Cammini minimi in DAG: SSSP-DAG
DAG-Shortest-Path(G,w,s)1 ordina topologicamente i vertici di G2 Initialize-Single-Source(G,s)3 foreach vertice u nell’ordine topologico do 4 foreach vertice v Adj[u] do5 Relax(u,v,w)
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).
25/31
Cammini minimi in DAG: esempio
0 5 2 7 -1 -2
6 1
3 42
26/31
Cammini minimi in DAG: esempio
0 5 2 7 -1 -2
6 1
3 42
27/31
Cammini minimi in DAG: esempio
6 25 2 7 -1 -2
6 1
3 42
0
28/31
Cammini minimi in DAG: esempio
6 6 4 5 2 7 -1 -2
6 1
3 42
0 2
29/31
Cammini minimi in DAG: esempio
5 4 5 2 7 -1 -2
6 1
3 42
0 2 6
30/31
Cammini minimi in DAG: esempio
3 5 2 7 -1 -2
6 1
3 42
0 2 6 5
31/31
Cammini minimi in DAG: esempio
5 2 7 -1 -2
6 1
3 42
0 2 6 5 3
32/31
Cammini minimi in DAG: complessità
T(V,E) = (V + E) + (V) + E (1) = (V + E)