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)