Cammini minimi con sorgente singola. Dato un grafo (orientato o non orientato) G = (V,E) con...

transcript

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.

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.

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:

Algoritmo di Dijkstra: Relax

Relax(u, v, w)1 if d[v] > d[u] + w(u,v)2 thend[v] = d[u] + w(u,v)3 p[v] = u

Rilassamento di un arco (u,v): verifica se è possibile migliorare il cammino minimo per v passante per u trovato fino a quel momento.Se si, si aggiornano d[v] e p[v].

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. for u 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.

Algoritmo di Dijkstra

Algoritmo di Dijkstra: esempio

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.

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)

Algoritmo di Bellman-Ford

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

Algoritmo di Bellman-Ford: esempio

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.

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)

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

Cammini minimi in DAG: esempio

0 5 2 7 -1 -2

6 25 2 7 -1 -2

6 6 4 5 2 7 -1 -2

5 4 5 2 7 -1 -2

3 5 2 7 -1 -2

0 2 6 5

5 2 7 -1 -2

0 2 6 5 3

Cammini minimi in DAG: complessità

T(V,E) = (V + E) + (V) + E (1) = (V + E)

Cammini minimi con sorgente singola. Dato un grafo (orientato o non orientato) G = (V,E) con...

Documents