1

1/185

Algoritmi e Programmazione Avanzata - teoria

2/185

Che cosa c’è nella lezione

Questa lezione si occupa di teoria dei grafi:

la rappresentazione dei grafi

le visite dei grafi

gli alberi ricoprenti minimi

i cammini minimi.

2

3/185

Algoritmi e Programmazione Avanzata - teoria

4/185

Rappresentazione

Tramite:

lista di adiacenza;

matrice di adiacenza.

3

5/185

Lista di adiacenza

Dato G = (V, E), lista di adiacenza:

vettore A di |V| elementi;

A[i] contiene il puntatore alla lista dei vertici adiacenti a i.

6/185

Esempio: grafo non orientato

5

1

4

2

3

1

2

3

4

5

2

5

1

A1

2

5

5

4

2

3

3

4

4

2

4

7/185

Esempio: grafo orientato

1

2

3

4

5

2

3 4

3

5

1 2

5

1

4

2

3

8/185

Esempio: grafo orientato pesato

1

2

3

4

5

2/3

3/5 4/4

3/7

5/1

1/5 2/6

5

1

4

2

3

3

56

1

4

5

7

5

9/185

Vantaggi/svantaggi 1/2

Grafi orientati:elementi complessivi nelle liste = 2|E|

Grafi non orientati:elementi complessivi nelle liste = |E|

Complessità spazialeS(n) = O(max(|V|, |E|)) = O(|V+E|)

⇒ vantaggioso per grafi sparsi.

10/185

Vantaggi/svantaggi 2/2

Svantaggi:

verifica dell’esistenza di arco (u,v) mediantescansione della lista di adiacenza di u;

uso di memoria per i pesi dei grafi pesati.

6

11/185

Matrice di adiacenza

Dato G = (V, E), matrice di adiacenza:

matrice A di |V| x |V| elementi

1 se (i, j) ∈ EA[i,j] =

0 se (i, j) ∉E

grafi non orientati: A simmetrica.

12/185

Esempio: grafo non orientato

5

1

4

2

3

1 2 3 4 51

2

345

01 10 1 1

11 0 0

0 01 0 10 11 1 01 01 0 1

A

7

13/185

Esempio: grafo orientato

1 2 3 4 51

2

345

00 00 1 1

01 0 0

0 00 1 00 10 0 01 01 0 0

A

5

1

4

2

3

14/185

Esempio: grafo orientato pesato

1 2 3 4 51

2

345

00 00 5 4

03 0 0

0 00 7 00 10 0 05 06 0 0

A

5

1

4

2

3

3

56

1

4

5

7

8

15/185

Esempio: grafo orientato pesato

Complessità spaziale

S(n) = Θ(|V|2)⇒ vantaggioso per grafi densi

No costi aggiuntivi per i pesi

Accesso efficiente alla topologia del grafo.

16/185

Algoritmi e Programmazione Avanzata - teoria

9

17/185

Algoritmi di visita

Visita di un grafo G=(V, E):

a partire da un vertice dato s, seguendo gliarchi con una certa strategia, elencare i verticiincontrati.

Algoritmi:

in ampiezza (breadth-first search, BFS);

in profondità (depth-first search, DFS).

18/185

Visita in ampiezza: principi base 1/2

Scoperta di un vertice: prima volta che si incontra nella visita.

Ampiezza: espande tutta la frontiera travertici già scoperti/non ancora scoperti(usa coda Q).

Vertici:

bianchi: non ancora scoperti;grigi: scoperti, ma non completati;neri: scoperti e completati.

10

19/185

Dato vertice u:

d[u] = distanza di u da s;

π(u): padre di u nell’albero della visita.

Visita in ampiezza: principi base 2/2

20/185

Algoritmo 1/2

Inizializzazione

d[s]=0, π[s] = NIL, colore[s] = grigio

altri vertici u: d[u]=∞, π[u] = NIL, colore[u] = bianco

Q ={s}.

11

21/185

Algoritmo 2/2

Fintanto che Q non diventa vuoto:

estrai da Q l’elemento in testa u

∀ vertice v bianco e adiacente ad u

- d[v] = d[u] +1, colore[v] = grigio, π[v] = u- inserisci v in Q

colore[u] = nero.

22/185

Esempio

r s t u

w x y

π

v

Q

12

23/185

Esempio

∞

∞

∞∞

∞∞ ∞

0

sπQ

r s t u

w x yv

s

24/185

Esempio

1

∞

∞∞

1∞ ∞

0

sπQ

r s t u

w x yv

r w

r w

13

25/185

Esempio

1

∞

∞∞

12 ∞

0

sπQ

r s t u

w x yv

w v

r w

v

26/185

Esempio

1

2

∞2

12 ∞

0

sπQ

r s t u

w x yv

v t

r w

x

xv t

14

27/185

Esempio

1

2

∞2

12 ∞

0

sπQ

r s t u

w x y

t x

r w

xv t

v

28/185

Esempio

1

2

32

12 ∞

0

sπQ

r s t u

w x y

x u

r w

xv t

u

v

15

29/185

Esempio

1

2

32

12 3

0

sπQ

r s t u

w x y

u y

r w

xv t

u y

v

30/185

Esempio

1

2

32

12 3

0

sπQ

r s t u

w x y

y

r w

xv t

u y

v

16

31/185

Esempio

1

2

32

12 3

0

sπQ

r s t u

w x y

r w

xv t

u y

v

32/185

Complessità

Operazioni sulla coda

17

33/185

Complessità

O(|V|)

Operazioni sulla coda

34/185

Complessità

Operazioni sulla coda

Scansione delle liste di adiacenza

18

35/185

Complessità

O(|E|)

Operazioni sulla coda

Scansione delle liste di adiacenza

36/185

Complessità

Operazioni sulla coda

Scansione delle liste di adiacenza

T(n) = O(|V|+|E|).

19

37/185

Proprietà 1/2

RaggiungibilitàA partire da un vertice s:

determina tutti i vertici raggiungibili da s

38/185

Proprietà 2/2

Cammini minimi: la visita in ampiezza determina la minima distanza tra s e ogni vertice raggiungibile da esso.

s

r w

v t x

u y

π

Cammino minimo da s a u:s, w, t, ulunghezza = 3

20

39/185

Visita in profondità

A partire da un vertice s:

visita tutti i vertici del grafo (raggiungibili da s e non)

etichetta ogni vertice v con tempo di scoperta/tempodi fine elaborazione d[v]/f[v]

etichetta ogni arco:- grafi orientati: T(ree), B(ackward), F(orward), C(ross)- grafi non orientati: T(ree), B(ackward)

genera una foresta di alberi della visita in profondità.

40/185

Principi base

Profondità: espande l’ultimo vertice scopertoche ha ancora vertici non ancora scoperti adiacenti

Scoperta di un vertice: prima volta che si incontra nella visita

Vertici:

bianchi: non ancora scopertigrigi: scoperti, ma non completati

neri: scoperti e completati.

21

41/185

Strutture dati 1/2

Grafo come lista delle adiacenze

Tempo discreto time

Vettore d dei tempi di scoperta

Vettore f dei tempi di fine elaborazione

Vettore colore.

42/185

Strutture dati 2/2

Vettore π dei predecessori (per costruire gli alberi di visita in profondità)

Etichette degli archi T, B, F, C.

22

43/185

Algoritmo 1/2

Inizializzazione

π[u] = NIL, colore[u] = bianco

time = 0

∀ vertice u bianco, visita ricorsiva

44/185

Algoritmo 2/2

Visita ricorsiva da u:

colore[u] = grigio, d[u] = time++

∀ vertice v bianco e adiacente a u - π[v] = u, visita ricorsiva a partire da v

colore[u] = nero

f[u] = time++

23

45/185

Esempio

time = 0 π

r s t

v w x

46/185

Esempio

time = 1 π

r s t

v w x

1/

r

24

47/185

Esempio

time = 2 π

r s t

v w x

1/

r

2/

s

48/185

Esempio

time = 3 π

r s t

v w x

1/

r

2/

s

3/

w

25

49/185

Esempio

time = 4 π

r s t

v w x

1/

r

2/

s

3/4

w

50/185

Esempio

time = 5 π

r s t

v w x

1/

r

2/5

s

3/4

w

26

51/185

Esempio

time = 6 π

r s t

v w x

1/

r

2/5

s

3/4

w

6/

v

52/185

Esempio

time = 7 π

r s t

v w x

1/

r

2/5

s

3/4

w

6/7

v

27

53/185

Esempio

time = 8 π

r s t

v w x

1/8

r

2/5

s

3/4

w

6/7

v

54/185

Esempio

time = 9 π

r s t

v w x

1/8

r

2/5

s

3/4

w

6/7

v

t

9/

28

55/185

Esempio

time = 10 π

r s t

v w x

1/8

r

2/5

s

3/4

w

6/7

v

t

9/

10/

x

56/185

Esempio

time = 11 π

r s t

v w x

1/8

r

2/5

s

3/4

w

6/7

v

t

9/

10/11

x

29

57/185

Esempio

time = 12 π

r s t

v w x

1/8

r

2/5

s

3/4

w

6/7

v

t

9/12

10/11

x

58/185

Complessità

Inizializzazione

30

59/185

Complessità

Inizializzazione

Θ(|V|)

60/185

Complessità

Inizializzazione

Visita ricorsiva da u

31

61/185

Complessità

Inizializzazione

Visita ricorsiva da uΘ(|E|)

62/185

Complessità

Inizializzazione

Visita ricorsiva da u

T(n) = Θ(|V|+|E|)

32

63/185

Classificazione degli archi

Grafo orientato:

T: archi dell'albero della visita in profondità

B: connettono un vertice ad un suo antenato nell’albero

F: connettono un vertice ad un suo discendente nell’albero

C: archi rimanenti.

Grafo non orientato: solo archi T e B.

64/185

Estensione della visita

Quando si incontra un arco (u,v) si considera il colore del vertice v in quel momento:

se colore[v]=bianco, (u,v) è T

se colore[v]=grigio, (u,v) è B

se colore[v]=nero:- se d[u]<d[v]) (u,v) è F- se d[u]>d[v]) (u,v) è C.

33

65/185

Esempio

b a s e

c d f g

b a

d

7/8 12/13

11/16T

T

14/15

BB

3/6 2/9

TC

s e

c f g

4/5

1/10

C

T

T

C C

TF

66/185

Esempio

s

a

b

c

d

e

f g

T

T

T

T

T T

B

B

C

C

C

C

F

Sovente si “ridisegna” il grafo a partire dagli alberi della visita in profondità.

34

67/185

Algoritmi e Programmazione Avanzata - teoria

68/185

Alberi ricoprenti minimi

G=(V,E) grafo non orientato, pesato w: E→R e connesso

Albero ricoprente minimo (non unico)

grafo G'=(V, T) dove T⊆E

aciclico

minimizza w(T)=Σ w(u,v).

Aciciclità e copertura di tutti i vertici ⇒ G’ è un albero

35

69/185

Approccio greedy

Approccio greedy:

a ogni passo, scelta della soluzione localmente ottima;

non garantisce soluzione globalmente ottima.

70/185

Algoritmo generico

A= sottoinsieme di albero ricoprente minimo, inizialmente vuoto

Fintanto che A non è un albero ricoprente minimo, aggiungi ad A un arco (u,v) “sicuro”

Invarianza: (u,v) sicuroaggiunto a un sottoinsieme di un albero ricoprente minimo produce ancora un sottoinsieme di un albero ricoprente minimo.

36

71/185

Tagli e archi 1/2

G=(V,E) grafo non orientato, pesato, connesso.

Taglio = partizione di V in S e V-SV = S∪ V-S e S ∩ V-S = ∅

(u,v) ∈ E attraversa il taglio ⇔ u∈S e v∈V-S (o viceversa).

72/185

Tagli e archi 2/2

Un taglio rispetta un insieme A di archi se nessun arco di A attraversa il taglio.

Un arco si dice leggero se ha peso minimo tra gli archi che attraversano il taglio.

37

73/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9

S

V-S

74/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9

S

V-S

(b,c) attraversa il taglio

38

75/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9

S

V-S

il taglio rispetta A A={(a,b), (c,f), (f,g), (g,h)}

76/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9

S

V-S

(c,d) è un arco leggero

39

77/185

Archi sicuri: teorema

G=(V,E) grafo non orientato, pesato, connesso.

A = sottoinsieme di un qualche albero ricoprente minimo di G;

(S,V-S) taglio qualunque che rispetta A;(u,v) un arco leggero che attraversa (S,V-S).

⇒ (u,v) è sicuro per A.

78/185

Archi sicuri: corollario

G=(V,E) grafo non orientato, pesato, connesso.

A = sottoinsieme di un qualche albero ricoprente minimo di G;C albero nella foresta GA= (V,A);(u,v) un arco leggero che connette C ad un'altra componente in GA .

⇒ (u,v) è sicuro per A.

40

79/185

Algoritmo di Kruskal

Basato su algoritmo generico

Corollario per determinare l’arco sicuro:

foresta di alberi, inizialmente vertici singoli;

ordinamento degli archi per pesi crescenti;

iterazioneselezione di un arco sicuro: arco di peso minimo che connette 2 alberi generando un albero;

terminazione: considerati tutti i vertici.

80/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9

41

81/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9

82/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9

42

83/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9

84/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9

43

85/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9

86/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9

44

87/185

Complessità

Dipende dalle strutture dati utilizzate.

Con strutture efficienti T(n) = O(|E|lg|E|).

88/185

Algoritmo di Prim

Basato sull’algoritmo generico

Uso del teorema per determinare l’arco sicuro:

inizialmente A = {r} (r = radice dell’albero)

iterazione: arco di peso minimo che connette un vertice di A con un vertice di V-A;

terminazione: considerati tutti i vertici.

45

89/185

Struttura dati

Coda a priorità: contiene tutti i vertici v non appartenenti ad A.

key[v] = minimo tra i pesi degli archi che collegano v a un qualunque vertice in A.

Se v non è collegato a nessun vertice in A, allora key[v]=∞.

90/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9A

V-A

r

46

91/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9A

V-A

92/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9A

V-A

47

93/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9A

V-A

94/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9A

V-A

48

95/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9A

V-A

96/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9A

V-A

49

97/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9A

V-A

98/185

Esempio

b c d

h g f

a ei

4

8

11

7 6

1 2

2

8 7

4 14

10

9A

50

99/185

Complessità

T(n) = O(|V|lg|V| + |E|lg|V|) = O(|E|lg|V|)

Con strutture dati particolari (heap di Fibonacci) T(n) = O(|E| + |V|lg|V|).

100/185

Algoritmi e Programmazione Avanzata - teoria

51

101/185

Cammini minimi

G=(V,E) grafo orientato, pesato (w: E→R)

Definizioni:peso w(p) di un cammino p:

w(p) = Σi=1kw(vi-1, vi)

peso δ(u,v) di un cammino minimo da u a v:

min{w(p): se ∃ u →p v }δ(u,v) =

∞ altrimenti

Cammino minimo da u a v:qualsiasi cammino p con w(p) = δ(u,v)

102/185

Problemi classici

Cammini minimi:

da sorgente singola: cammino minimo e suo peso da s a ogni altro vertice v

- algoritmo di Dijkstra

- algoritmo di Bellman-Ford

con destinazione singola

tra una coppia di vertici

tra tutte le coppie di vertici.

52

103/185

Archi con pesi negativi

∃ (u,v) ∈ E per cui w(u,v) < 0 ma ∃ ciclo a peso < 0:

algoritmo di Djikstra: soluzione ottima non garantita;algoritmo di Bellman-Ford: soluzione ottima garantita.

∃ ciclo a peso < 0: problema non definito, ∃ soluzione:

algoritmo di Djikstra: risultato senza significato;algoritmo di Bellman-Ford: rileva ciclo <0.

104/185

Esempio

a b

s c d g

e f

3

5

2

-4

4

8

7

6

-3

3

-6

53

105/185

Esempio

a b

s c d g

e f

3

5

2

-4

4

8

7

6

-3

3

-6

0

3 -1

-∞

-∞-∞

5 11

106/185

Rappresentazione 1/2

Vettore dei predecessori:

parent(v) se ∃∀v∈V p[v] =

NIL altrimenti

Sottografo dei predecessori:

Gp=(Vp,Ep), dove

- Vp = {v ∈V: p[v] ≠ NIL} ∪ {s}- Ep = {(p[v], v) ∈ E : v ∈ Vp - {s}}

54

107/185

Rappresentazione 2/2

Albero dei cammini minimi:

G’ = (V’, E’) dove V’ ⊆ V e E’ ⊆ E

V’: insieme dei vertici raggiungibili da ss radice dell’albero∀v∈V’ l’unico cammino semplice da s a v in G’ è un cammino minimo da s a v in G

Nei grafi non pesati: algoritmo di visita in ampiezza.

108/185

Esempio

u v

s

x y

3

5

6

4

3

21 7 2

6

55

109/185

Esempio

u v

s

x y

3

5

6

4

3

21 7 2

6

0

3 9

115

110/185

Esempio

u v

s

x y

3

5

6

4

3

21 7 2

6

0

3 9

115

56

111/185

Fondamenti teorici 1/3

Lemma: un sottocammino di un cammino minimo è un cammino minimo.

G=(V,E): grafo orientato, pesato w: E→R. p=<v1, v2, …, vk>: un cammino minimo da v1 a vk. ∀i, j 1≤i≤j≤k, pij=<vi,vi+1,…,vj>: sottocammino di p da vi a vj.

pij è un cammino minimo da vi a vj.

112/185

Fondamenti teorici 2/3

Corollario:

G=(V,E): grafo orientato, pesato w: E→R.

Cammino minimo p da s a v decomposto in

un sottocammino da s a uun arco (u,v).

Allorad(s,v)=d(s,u)+w(u,v)

57

113/185

Fondamenti teorici 3/3

Lemma:

G=(V,E): grafo orientato, pesato w: E→R.

∀(u,v)∈E

d(s,v) ≤ d(s,u) + w(u,v)

114/185

Rilassamento

d[v]: stima (limite superiore) del peso del cammino minimo da s a vinizialmente:

∀ v ∈ V d[v]=∞, π[v] = NIL; d[s] = 0

Rilassare: (= aggiornare) d[v] e π [v] verificando se conviene il cammino da s a u e l’ arco (u,v):

if (d[v]>d[u]+w(u,v)) {d[v] = d[u]+w(u,v);

π [v]←u;}

58

115/185

Esempio

u v

5 9

2

u v

5 7

2

Rilassamento

d[v] =9d[u] = 5w(u,v) = 2d[v]>d[u] + w(u,v)

d[v] = 7π[v] = ucammino minimo da s a v =cammino minimo da s a u + arco (u,v)

116/185

Esempio

u v

5 6

2

u v

5 7

2

Rilassamento

d[v] =6d[u] = 5w(u,v) = 2d[v]<d[u] + w(u,v)

Il rilassamento non ha avuto effetto

59

117/185

Proprietà 1/3

Lemma:

G=(V,E): grafo orientato, pesato w: E→R.

(u,v)∈E

Dopo il rilassamento di (u,v) si ha che:

d[v] ≤ d[u] + w(u,v)

118/185

Proprietà 2/3

Lemma:

G=(V,E): grafo orientato, pesato w: E→R.

sorgente s ∈ V

inizializzazione di d e π

∀ v ∈ V d[v] ≥ δ(s,v)

per tutti i passi di rilassamento sugli archi

quando d[v] = δ(s,v), allora d[v] non cambia più.

60

119/185

Proprietà 3/3

Lemma:

G=(V,E): grafo orientato, pesato w: E→R.sorgente s ∈ Vcammino minimo da s a v composto da

cammino da s a uarco (u,v)

inizializzazione di d e πapplicazione del rilassamento su (u,v)

se prima del rilassamento d[u] = δ(s,u)dopo il rilassamento d[v] = δ(s,v).

120/185

Applicazione

Rilassamento:

applicato 1 volta ad ogni arco (Dijkstra) o più volte (Bellman-Ford);

ordine con cui si rilassano gli archi.

61

121/185

Algoritmo di Dijkstra

Ipotesi: ∃ archi a peso < 0

Strategia: greedy

S: insieme dei vertici il cui peso di cammino minimo da s è già stato determinato

V-S: coda a priorità Q dei vertici ancora da stimare. Termina per Q vuoto:

estrae u da V-S (d[u] minimo)inserisce u in Srilassa tutti gli archi uscenti da u.

122/185

Esempio

u v

s

x y

10

5

1

9

7

23 6 4

2

62

123/185

Esempio

u v

s

x y

10

5

1

9

7

23 6 4

2

S={}Q={s/0, u/∞,v/∞, x/∞, y/∞}

0

∞ ∞

∞ ∞

124/185

Esempio

u v

s

x y

10

5

1

9

7

23 6 4

2

0

∞

∞

10

5

S={s} relax (s,u), (s,x)Q={x/5, u/10,v/∞, y/∞}

63

125/185

Esempio

u v

s

x y

10

5

1

9

7

23 6 4

2

0

8

5

14

7

S={s, x} relax (x,u), (x,v), (x,y)Q={y/7, u/8,v/14,}

126/185

Esempio

u v

s

x y

10

5

1

9

7

23 6 4

2

0

8

5

13

7

S={s, x, y} relax (y,s), (y,v)Q={u/8,v/13}

64

127/185

Esempio

u v

s

x y

10

5

1

9

7

23 6 4

2

0

8

5

9

7

S={s, x, y, u} relax (u,v), (u,x)Q={v/9}

128/185

Esempio

u v

s

x y

10

5

1

9

7

23 6 4

2

0

8

5

9

7

S={s, x, y, u, v} relax (v,y)Q={}

65

129/185

Complessità

V-S: coda a priorità Q dei vertici ancora da stimare.

130/185

Complessità

V-S: coda a priorità Q dei vertici ancora da stimare.

Θ(|V|)

66

131/185

Complessità

V-S: coda a priorità Q dei vertici ancora da stimare. Termina per Q vuoto

estrae u da V-S (d[u] minimo)

132/185

Complessità

V-S: coda a priorità Q dei vertici ancora da stimare. Termina per Q vuoto

estrae u da V-S (d[u] minimo) O(lg|V|)

67

133/185

Complessità

V-S: coda a priorità Q dei vertici ancora da stimare. Termina per Q vuoto

estrae u da V-S (d[u] minimo)inserisce u in Srilassa tutti gli archi uscenti da u

134/185

Complessità

V-S: coda a priorità Q dei vertici ancora da stimare. Termina per Q vuoto

estrae u da V-S (d[u] minimo)inserisce u in Srilassa tutti gli archi uscenti da u

O(lg|V|) O(|E|)

68

135/185

Complessità

V-S: coda a priorità Q dei vertici ancora da stimare. Termina per Q vuoto

estrae u da V-S (d[u] minimo)inserisce u in Srilassa tutti gli archi uscenti da u

T(n) = O((|V|+|E|) lg |V|)

136/185

Algoritmo di Bellman-Ford

Ipotesi: possono ∃ archi a peso < 0

Rileva cicli < 0

Strategia: greedy

Inizializzazione di d

|V|-1 passi di rilassamento sugli archi

|V|esimo rilassamento:

diminuisce almeno una stima: ∃ciclo <0altrimenti soluzione ottima.

69

137/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-4

Archi in ordine lessicografico:(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

138/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

∞ ∞

∞∞(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 1

70

139/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

∞ ∞

∞∞(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 1

140/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

∞ ∞

∞∞(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 1

71

141/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

∞ ∞

∞∞(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 1

142/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

∞ ∞

∞∞(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 1

72

143/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

∞ ∞

∞∞(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 1

144/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

∞ ∞

∞∞(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 1

73

145/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

∞ ∞

∞∞(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 1

146/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

∞ ∞

∞(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 16

74

147/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

∞

∞(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 16

7

148/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

∞

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 26

7

11

75

149/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

∞

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 26

7

11

150/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 26

7

11

2

76

151/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 26

7

11

2

152/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 26

7

4

2

77

153/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 26

7

4

2

154/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 26

7

4

2

78

155/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 26

7

4

2

156/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 26

7

4

2

79

157/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 26

7

4

2

158/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 36

7

4

2

80

159/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 36

7

4

2

160/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 36

7

4

2

81

161/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 32

7

4

2

162/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 32

7

4

2

82

163/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 32

7

4

2

164/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 32

7

4

2

83

165/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 32

7

4

2

166/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 32

7

4

2

84

167/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 32

7

4

2

168/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 42

7

4

2

85

169/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 42

7

4

2

170/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 42

7

4

-2

86

171/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 42

7

4

-2

172/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 42

7

4

-2

87

173/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 42

7

4

-2

174/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 42

7

4

-2

88

175/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 42

7

4

-2

176/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 42

7

4

-2

89

177/185

Esempio

u v

z

x y

6

7

5

-3

2

8 7

9

-2

-40

(u,v)(u,x)(u,y)(v,u)(x,v)(x,y)(y,v)(y,z)(z,u)(z,x)

Passo 42

7

4

-2

178/185

Esempio

Al |V|-esimo passo di rilassamento non diminuisce alcuna stima:

terminazione con soluzione ottima

90

179/185

Complessità

Inizializzazione

180/185

Complessità

Inizializzazione O(|V|)

91

181/185

Complessità

Inizializzazione

|V| - 1 passi di rilassamento sugli archi

182/185

Complessità

Inizializzazione

|V| - 1 passi di rilassamento sugli archi

O(|V||E|)

92

183/185

Complessità

Inizializzazione

|V| - 1 passi di rilassamento sugli archi

|V| - esimo rilassamento

184/185

Complessità

Inizializzazione

|V| - 1 passi di rilassamento sugli archi

|V| - esimo rilassamento

O(|E|)

93

185/185

Complessità

Inizializzazione

|V| - 1 passi di rilassamento sugli archi

|V| - esimo rilassamento

T(n) = O(|V||E|)