Esercizio Trovare il percorso minimo da b ad ogni altro vertice c 4 2 14 3 4 4 ef d b a 5 1 1 04 2...

Esercizio

• Trovare il percorso minimo da b ad ogni altro vertice

c

42

1 4

3

4

4

ef

d

b

a5

11

0 4

2

3 5

8

c

42

1 4

3

4

4

ef

d

b

a5

11

0u

1

1

v w x

ts0

3 -5

2

11

1 1

u

1

1

v w x

ts0

1

1

3 -5

2

11

1 1

1

u

1

1

v w x

ts0

1 4

1

3

3 -5

2

11

1 11

u

1

1

v w x

ts0

1 2

1

3

3 -5

2

11

1 12

u

1

1

v w x

ts0

1 2

1

3

3 -5

2

11

1 12

u

1

1

v w x

ts0

1 2

1

3

3

3 -5

2

11

1 13

u

1

1

v w x

ts0

1 2

1

3

4

3 -5

2

11

1 1

3

u

1

1

v w x

ts0

1 2

1

3

3

3 -5

2

11

1 1

u

1

1

v w x

ts0

0 -1

1

-2

3

3 -5

2

11

1 1

u

1

1

v w x

ts0

1 2

1

3

3

3 -5

2

11

1 1

Soluzione di Dijkstra Soluzione Ottimale

Problems with Dijkstra’s Algorithm

Algoritmo di Bellman-Ford

• Inizalmente, d[s] = 0 e d[u] = per u s• Vengono fatte |V| - 1 passate• Ad ogni passata, applica il rilassamento ad ogni

arco

Bellman_Ford(G,s) Inizializza(G,s,d) for i = 1 to |V|-1 do for each arco (u,v) in E do relax(u,v,w) for each arco (u,v) in E do if d[v] > d[u] + w(u,v) then return FALSE return TRUE

Tempo = O(|V||E|)

u

1

1

v w x

ts0

3 -5

2

11

1 1

u

1

1

v w x

ts0

1

1

3 -5

2

11

1 1

u

1

1

v w x

ts0

1 4

1

3

3 -5

2

11

1 1

u

1

1

v w x

ts0

1 2

1

-2

3

3 -5

2

11

1 1

u

1

1

v w x

ts0

1 2

1

-2

3

3 -5

2

11

1 1

u

1

1

v w x

ts0

0 -1

1

-2

3

3 -5

2

11

1 1

u

1

1

v w x

ts0

1 -1

1

-2

3

3 -5

2

11

1 1

Bellman-Ford: correttezza

Teorema: Se eseguiamo l’algoritmo di Bellman-Ford su un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali, e un vertice sorgente s:

• se non esistono cicli negativi raggiungibili da s, allora l’algoritmo ritorna TRUE, d[v] = (s,v) per tutti i vertici v in V e il grafo dei predecessori Gp è l’albero dei percorsi minimi;

• se esistono cicli negativi raggiungibili da s, allora l’algoritmo ritorna FALSE.


Lemma 8: Se eseguiamo l’algoritmo di Bellman-Ford su un grafo pesato orientato G = (V, E), con funzione di peso w: E che mappa archi in pesi a valori reali, e un vertice sorgente s e non esistono cicli negativi raggiungibili da s, allora alla terminazione d[v] = (s,v) per tutti i vertici v in V.


Dimostrazione: Sia v un vertice raggiungibile da s e p=<v0,v1,…,vk> un percorso minimo tra s e v (v0=s e vk=v).

Poiché p deve essere semplice, non può avere più di |V|-1 archi (cioè k |V|-1).

Per induzione su k dimostriamo che d[vi] = (s,vi) dopo i passi sugli archi di G e che poi non cambia più.

Poiché vengono fatte esattamente |V|-1 passi dall’algoritmo, questo è sufficiente a dimostrare il lemma.


Dimostrazione: Sia v un vertice raggiungibile da s e p=<v0,v1,…,vk> un percorso minimo tra s e v (v0=s e vk=v).

Per induzione su k dimostriamo che d[vi] = (s,vi) dopo i passi sugli archi di G e che poi non cambia più.

Base: d[v0] = d[s] = 0 = (s,s) e il Lemma 4 garanti-sce che non cambia più.

Induzione: Assimuamo che valga per i-1 cioè che d[vi-1] = (s,vi-1) dopo il passo i-1.

Si rilassa l’arco (vi-1,vi) al passo i e per il Lemma 5 concludiamo che d[vi] = (s,vi) da allora in poi.


Corollario 3: Sia G = (V, E) un grafo pesato orientato con funzione di peso w: E che mappa archi in pesi a valori reali, e s un vertice sorgente. Allora, per ogni nodo v S, esiste un percorso da s a v se e solo se alla terminazione dell’algoritmo di Bellman-Ford vale d[v] < .

Dimostrazione: Simile al Lemma 8 precedente.


Dimostrazione teorema:caso 1: Non ci sono cicli negativi raggiungibili da s Allora per ogni v V vale d[v] = (s,v) infatti, se v è raggiungibile da s Lemma 8 se v non è raggiungibile da s Corollario 3 Da questo e dal Lemma 7 sappiamo inoltre che Gp

è un albero dei percorsi minimi. L’algoritmo restituisce TRUE poiché, per ogni

(u,v) E, vale che d[v] = (s,v) e per Lemma 2, d[v] = (s,v) (s,u) + w(u,v) = d[u] + w(u,v)

Quindi nessuno dei controlli dell’algoritmo (dopo il while) è verificato, perciò ritorna TRUE.

Contraddizione!


Dimostrazione teorema:caso 2: Ci sono cicli negativi raggiungibili da s, e sia

p=<v0,v1,…,vk> uno di tali cicli (v0 = vk).

Allora w(vi-1,vi ) < 0 i=1…k

Supponiamo che l’algoritmo ritorni TRUE. Allora d[vi] d[vi-1] + w(vi-1,vi ) per i = 1,…,k Sommando le disuguaglianze lungo il ciclo si ha

d[vi ] d[vi-1 ] + w(vi-1,vi ) i=1…k i=1…k i=1…k k

Ma come per il Lemma 6 otterremo che

0 w(vi-1,vi ) i=1…k k

• Trovare il percorso minimo da u ad ogni altro vertice

Esercizio

0

w

6

7

9

5

-4

xy

v

u8 7

-2

-3

2 4

0

7 -2

w

6

7

9

5

-4

xy

v

u8 7

-2

-3

Grafi: Percorsi minimi

• Percorsi minimi da una singola sorgente• Trovare il percoso minimo dalla sorgente s ad ogni

altro vertice

• Percorsi minimi per tutte le coppie• Trovare il percoso minimo tra tutte le coppie di

vertici• Input: G = (V, E) un grafo orientato e

w: E una funzione di peso.• Output: per ogni coppia di vertici i,j V il

percorso minimo tra i e j.

Una tabella D=(dij ) contenente la distanza minima tra i vertici i e j.



altro vertice


vertici

• Eseguire l’algoritmo di Dijkstra |V| volte (ma solo se i pesi sono non-negativi)

• Eseguire l’algoritmo di Bellman-Ford |V| volte



altro vertice


vertici• Eseguire l’algoritmo di Dijkstra |V| volte (ma solo se i pesi sono non-negativi)

• Eseguire l’algoritmo di Bellman-Ford |V| volte

O(|V|3)

O(|V|2|E|) O(|V|4)grafo denso

O(|V||E| log|V|)o

Grafi: Percorsi minimi• Percorsi minimi per tutte le coppie

• Trovare il percoso minimo tra tutte le coppie di vertici• Input: G = (V, E) un grafo orientato

w: E una funzione di peso

Il grafo può allora essere rappresentato come una matrice di adiacenza W = (wij ) di dimensione nn, così definita:

E(i,j)ejiseE(i,j)ejisejidipeso

jisewij

),(

0

Grafi: Percorsi minimi• Percorsi minimi per tutte le coppie

• Trovare il percoso minimo tra tutte le coppie di vertici• Output: per ogni coppia di vertici i,j V il



ijejise

ijejisejijise

d ij da ileraggiungib ènon

da ileraggiungib è

),(0


Una tabella P=(pij ) contenente il predecessore di j lungo il percorso minimo da i a j.

ijejiseNilj

keijejisek

jiseNil

pij

da ileraggiungib ènon

minimo percorso il lungo di

repredecesso il è da ileraggiungib è


vertici• Output: per ogni coppia di vertici i,j V il



Percorsi minimi: con matrici

Programmazione Dinamica

Caratterizzare la struttura di una soluzione ottima

Definire ricorsivamente il valore di una soluzione ottima

Calcolare il valore di una soluzione ottima “bottom-up”

Cotruzione di una soluzione ottima.

Carattedizzazione della soluzione ottima

Struttura della soluzione ottima.

Data la matrice W = (wij ) di adiacenza del grafo pesato, consideriamo il percorso minimo p tra i vertici i e j.

Suppimiano che p contenga al più k archi.Assumendo che non esistano cicli negativi, k sarà

allora finito.• Se i = j, allora p ha peso 0 e nessun arco.


Struttura della soluzione ottima.

Data la matrice W = (wij ) di adiacenza del grafo pesato, consideriamo il percorso minimo p tra i vertici i e j.

Suppimiano che p contenga al più k archi.Assumendo che non esistano cicli negativi, k sarà

allora finito. p’• Se i j, allora p sarà della forma i m j dove

p’ contiene al più k-1 archi ed è un percorso minimo tra i e m (Lemma 1).Ma allora (Corollario 2) (i,j) = (i,m) + wm j

Definizione ricorsiva della soluzione ottima

• dij(k) = il peso del percorso minimo tra i vertici

vi e vj usando al più k archi.• Vogliamo calcolare dij

(|V|-1) per tutte le coppie i,j.• Iniziamo a calcolare il caso base, qundo non

abbiamo alcun vertice a disposizione per formare percorsi, cioè quando k=0.

jisejised ij

0)0(




(|V|-1) per tutte le coppie i,j. • Supponiamo di avere a disposizione la matrice dij

(k-1) dei

percorsi minimi contenenti al più k-1 archi.• Il percorso minimo di tra vj e vj , o contiene k-1 archi e ha

costo dij(k-1),

• o contiene k archi e sarà composto da un percorso minimo di k-1 archi più un nodo vm con un arco a vi

e dal passo sappiamo che in tal caso il costo sarà dij(k) =

dim(k-1) + wm j




(|V|-1) per tutte le coppie i,j.

mj

kim

nm

kij

kij wddd )1(

1

)1()( min,min

mjk

imnm

wd

)1(

1min

Poiché wjj=0, quindi se

m=j, dij(k-1) =dij

(k-1) + wj j


• Come si calcolano i costi effettivi dei percorsi minimi?

• Quante matrici D(k) = (dij(k)) dobbiamo calcolare?

• Per quale valore di k otteniamo in D(k) i pesi (costi) dei percorsi minimi?

mj

kim

nm

kij

kij wddd )1(

1

)1()( min,min

mjk

imnm

wd

)1(

1min

Poiché wjj=0, quindi se

m=j, dij(k-1) =dij

(k-1) + wj j





• Se, come da ipotesi, il grafo non contiene cicli di peso negativo,

• allora ogni percorso minimo sarà un percorso semplice con al più |V|-1 archi.

E quindi (i,j) = dij(|V|-1) = dij

(|V|) = dij(|V|+1) = ...

Calcolo del valore della soluzione ottima

• L’algoritmo riceve in ingresso la matrice W =

(wij ) di adiacenza del grafo pesato.• Viene quindi calcolata una sequenza di

matrici D(0) = D(1) = D(2) = … = D(|V|-1), dove per k=1,2,…,|V|-1 abbiamo D(k) = (dij

(k)).• La matrice D(|V|-1) conterrà i pesi dei percorsi

minimi.• La matrice D(|1) = W


Slow_All_Pair_Shst_Paths(W:matrice) n = righe[W] D(1) = W for k = 2 to n-1 do D(k) = Extend_Shst_Paths(D(k-1),W) return D(n-1)

• La procedura Extend_Shst_Paths è la proce-dura che, date le matrici D(k-1) e W calcola la matrice D(k) secondo la fomula

mjk

imnm

kij wdd

)1(

1

)( min

(n T(Extend_Shst_Path))


Extend_Shst_Paths(D,W:matrice) n = righe[D] “Sia D’ una nuova matrice nn” for i = 1 to n do for j = 1 to n do d’ij = for k = 1 to n do d’ij = min(d’ij,dim+wmj) return D’

• La procedura Extend_Shst_Paths è la procedura che, date le matrici D(k-1) e W calcola la matrice D(k)

secondo la fomula mjk

imnm

kij wdd

)1(

1

)( min

(n3)


Slow_All_Pair_Shst_Paths(W:matrice) n = righe[W] D(1) = W for k = 2 to n-1 do D(k) = Extend_Shst_Paths(D(k-1),W) return D(n-1)

• La procedura Extend_Shst_Paths è la proce-dura che, date le matrici D(k-1) e W calcola la matrice D(k) secondo la fomula

mjk

imnm

kij wdd

)1(

1

)( min

(n4)

0-524

043

102

8301

4321

k=1

7

-4

5

65 0

-5v1

v2

v3

v4

v5

2

4

-46

8

3

7

1

v2

v4

v5

7

1v1

v3

v4

v56

v1

v2

v3

v2

v3

4

v1

v5

v4

v1

v3

v4

2-5

v2

v5

v1 v2

v3

v5

v4

v1

v3

8

v2

3

v5

-4v4

0-524

043

102

8301

4321

k=1

7

-4

5

65 00-5-124

5043

1-4032

28301

4321

k=2

-2

11

7

-4

5

6185 0

v1

v3

v4

2-5

v2

v5

-4

v1

v2

v3

v4

v5

2

4

-46

-58

3

7

1

v2

v4

v5

7

1v1

v3

v4

v56

v1

v2

v3

v2

v3

4

v1

v5

v4

v1 v2

v3

v5

v4

v1

v3

8

v2

3

v5

-4 v4

6

41

7

2-5

2-5

0-5-124

5043

1-4032

28301

4321

k=2

-2

11

7

-4

5

6185 0

v1

v2

v3

v4

v5

2

4

-46

-58

3

7

1

v1 v2

v3

v5

v4

v1

v3

8

v2

3

v5

-4 v4

6

v1

v3

v4

2-5

v2

v5

-4

4

v2

v3

4

v1

v5

v4

1

7

7

v2

v4

v5

1v1

v3

2-5

v4

v56

v1

v2

v3

2-5

0-5-124

50473

1-4032

2-3301

4321

k=3

-2

11

-1

-4

5

61585 0

8 -5

-4 7

2

4

v1

v2

v3

v4

v5

2

4

-46

-58

3

7

1

v1 v2

v3

v5

v4

v1

v3

v4

2-5

v2

v5

-4

4

0-5-124

50473

1-4032

2-3301

4321

k=3

-2

11

-1

-4

5

61585 0

v1

v3

v2

3

v5

-4 v4

6

-5

v2

v4

v5

1v1

v3

2-5

-4v2

v3

4

v1

v5

v4

1

7

2

v4

v56

v1

v2

v3

2-5

4

0-5-124

50473

1-4032

2-3101

4321

k=4

-2

3

-1

-4

5

61585 0

-4 7

34


• Possiamo migliorare il tempo di esecuzione dell’algoritmo?

• In effetti vengono calcolate più matrici di quelle necessarie, o meglio matrici inutili.

D(1) = D(0) W = W D(2) = D(1) W = W2

D(3) = D(2) W = W3

D(4) = D(3) W = W4

…

D(n-1) = D(n-2) W = Wn-1

Calcolo del valore della soluzione ottima• Possiamo migliorare il tempo di esecuzione

dell’algoritmo?• In effetti vengono calcolate più matrici di

quelle necessarie, o meglio matrici inutili.

D(1) = D(0) W = W D(2) = D(1) W = D(1) D(1) = W2

D(3) = D(2) W = W3

D(4) = D(3) W = D(2) W W = D(2) D(2) = W4

…

D(2k) = D(k) D(k) = W2k

Come il prodotto di matrici, anche l’estensione è una operazione associativa


• Possiamo migliorare il tempo di esecuzione dell’algoritmo?

• In effetti vengono calcolate più matrici di quelle necessarie, o meglio matrici inutili.

• Cosa possiamo fare?

D(1) = D(0) W22 = W2 D(2) = D(1) D(1) = W2

D(4) = D(2) D(2) = W4

D(8) = D(4) D(4) = W8

…

D(2log n-1) = D(2log n-2) D(2log n-2) = W 2log n-1


• Cosa possiamo fare?

D(1) = D(0) W22 = W2 D(2) = D(1) D(1) = W2

D(4) = D(2) D(2) = W4

D(8) = D(4) D(4) = W 8

…

D(2log n-1) = D(2log n-2) D(2log n-2) = W 2log n-1

• Il fatto che dij(n-1) = dij

(n) = dij(n+1) = ... ci assicura che

poiché 2log(n-1) > n -1, allora D(2log n-1) = D(n-1). • Quindi possiamo fermarci non appena il valore di k

= 1,2,4,8,… supera n -1.


Fast_All_Pair_Shst_Paths(W:matrice) n = righe[W] D(1) = W k = 1 whilo k < n-1 do D(2

k) = Extend_Shst_Paths(D(k),D(k))

k = 2 k return D(k)

Il tempo di esecuzione sarà quindi (n3log n)


• Una volta che abbiamo calcolato la matrice delle distanze minime D = D(n-1), come pos-siamo ricostruire i percorsi minimi ?

• In altre parole come possiamo calcolare la matrice dei predecessori P = P(n-1) ?

• Si possono usare essenzialmente due metodi:• Calcolare una sequenza di matrici dei predecessori

P(k) per k=1,…,n-1 mentre calcoliamo D(k)

• Calcolare P direttamente da D (Esercizio 26-1.5)

Algoritmo di Floyd-Warshall

• Altro algoritmo di Programmazione Dinamica

• I pesi possono essere anche negativi, ma si assume sempre che non ci siano cicli negativi

• Si differenzia dal precedente per il tipo di sottostruttura della soluzione che utilizza e quindi per la nozione di sottoproblema.

• Miglioramento del tempo di esecuzione


Consideriamo i vertici intermedi di un percorso semplice p=<v1, v2 ,…, vl >.

Cioè l’insieme dei vertici {v2 ,v3 ,…, vl-1 }.

Se {1, 2 ,…, n} sono i vertici del grafo, prendia-mone un sottoinsieme {1, 2 ,…, k}.

Per ogni coppia di vertici i,j consideriamo i per-corsi che hanno i vertici solo in {1, 2 ,…, k}.

Sia inoltre p il percorso di peso minimo (e quindi anche semplice) tra di essi.

Che relazione c’è tra p e il percorso minimo tra i e j che ha i vertici solo in {1, 2 ,…, k-1}?



La relazione dipenderà dal fatto che k sia o meno un vertice intermedio del nuovo percorso minimo p!

Abbiamo cioè due casi:• k non è un vertice intermedio di p • k è un vertice intermedio di p



Abbiamo cioè due casi:• k non è un vertice intermedio di p

• k è un vertice intermedio di p

Allora tutti i vertici di p percorsi sono contenuti in {1, 2 ,…, k-1}.

Quindi, un percorso minimo tra i e j contenente solo vertici in {1, 2 ,…, k-1} è anche un percorso minimo tra i e j contenente solo vertici in {1, 2 ,…, k}.



Abbiamo cioè due casi:• k non è un vertice intermedio di p • k è un vertice intermedio di p

ki j p1 p2

Allora p può essere scomposto in due percorsi p1 e p2 che si

congiungono in k (ikj) p2p1

Per la sottostruttura, p1 e p2 sono percorsi minimi da i a k e da k a j con vertici in {1, 2 ,…, k-1}.

Infatti k non è un vertice intermedio né di p1 né di p2, e w(p) = w(p1) + w(p2) = (i,k) + (k,j)



vi e vj con vertici intermedi solo tra v1, v2, …, vk.

• Vogliamo calcolare dij(n) per tutte le coppie i,j.

• Iniziamo a calcolare il caso base, qundo non abbiamo vertici intermedi a disposizione per formare percorsi, cioè quando k=0.

ijij wd )0(


• dij(k) = il peso del percorso minimo tra i vertici i e

j usando solo {1,2,…,k} come possibili ver-tici intermedi.


• Supponiamo di avere a disposizione la matrice dij(k-1)

dei percorsi minimi che contengono solo vertici in {1,…,k-1}. Allora il percorso minimo di tra i e j ,

• o non contiene il vertice intermedio k, e ha quindi peso dij

(k-1),• o contiene k e sarà perciò composto dalla concatena-

zione del percorso minimo tra i e k e quello tra k e j. Il peso sarà quindi dij

(k) = dik(k-1) + dkj

(k-1) .


• dij(k) = il peso del percorso minimo tra i vertici vi e

vj usando solo v1, v2, …, vk come possibili vertici intermedi.


1,min

0)1()1()1(

)(

kseddd

ksewd k

kjk

ikk

ij

ijkij

Notate che ora l’indice k delle matrici è anche l’indice

del vertice intermedio





• Se, come da ipotesi, il grafo non contiene cicli di peso negativo,

• allora ogni percorso minimo sarà un percorso semplice con al più vertici intermedi in {1,2,…,n}

E quindi (i,j) = dij(n) = dij

(n+1) = dij(n+2) = ...


• L’algoritmo riceve in ingresso la matrice W =

(wij ) di adiacenza del grafo pesato.

• Viene quindi calcolata una sequenza di matrici D(0) = D(1) = D(2) = … = D(n), dove per k=0,1,2,…,n abbiamo D(k) = (dij

(k)).

• La matrice D(n) conterrà i pesi dei percorsi minimi.

• La matrice D(0) = W


j k

i

k

k-1

j

i

k

)1()1()1()( ,min kkj

kik

kij

kij dddd per k

1


Floyd_Warshall(D,W:matrice) n = righe[D] D(0) = W for k = 1 to n do for i = 1 to n

do for j = 1 to n do d(k)

ij = min(d(k-1)ij,d(k-1)

ik+d(k-1)kj)

return D(n)

• Calcola la sequenza di n matrici D(1), D(2),…, D(n)

secondo la formula

(n3)

)1()1()1()( ,min kkj

kik

kij

kij dddd

0-524

043

102

8301

4321

k=0

7

-4

5

65 0

-5v1

v2

v3

v4

v5

2

4

-46

8

3

7

1

v2

v4

v5

7

1v1

v3

v4

v56

v1

v2

v3

v2

v3

4

v1

v5

v4

v1

v3

v4

2-5

v2

v5

v1 v2

v3

v5

v4

v1

v3

8

v2

3

v5

-4 v4

0-524

043

102

8301

4321

k=0

7

-4

5

65 00-5524

043

102

8301

4321

k=1

-2

7

-4

5

65 0

3

v1

v3

v4

2-5

v2

v5

-4

v1

v2

v3

v4

v5

2

4

-46

-58

3

7

1

v2

v4

v5

7

1v1

v3

v4

v56

v1

v2

v3

v2

v3

4

v1

v5

v4

v1 v2

v3

v5

v4

v1

v3

8

v2

3

v5

-4 v4

v1

v2

v3

v4

v5

2

4

-46

-58

3

7

1

0-5524

043

102

8301

4321

k=1

-2

7

-4

5

65 0

v1

v3

v4

2-5

v2

3

v5

-4

0-5524

5043

102

48301

4321

k=2

-2

11

7

-4

5

65 0

v1

v3

8

v2

3

v5

-4 v4

1

7

1

v2

v3

4

v5

v4

v1

v2

v4

v5

7

1v1

v3

v4

v56

v1

v2

v3

v1 v2

v3

v5

v4

-5v1

v2

v3

v4

v5

2

4

-46

8

3

7

1

0-5524

5043

102

48301

4321

k=2

-2

11

7

-4

5

65 0

v1

v3

8

v2

3

v5

-4 v4

1

v2

v3

4

v5

7v4

1v1

v2

v4

v5

7

1v1

v3

v4

v56

v1

v2

v3

0-5-124

5043

102

48301

4321

k=3

-2

11

7

-4

5

65 0

v2

v5

-4

v1

v3

v4

2-5

3

4

3

v1 v2

v3

v5

v4

-5v1

v2

v3

v4

v5

2

4

-46

8

3

7

1 v1

v3

8

v2

3

v5

-4 v4

1

v2

v4

v5

7

1v1

v3

v4

v56

v1

v2

v3

0-5-124

5043

102

48301

4321

k=3

-2

11

7

-4

5

65 0

v2

v5

-4

v1

v3

v4

2-5

4

0-5-124

50473

1-4032

4-1301

4321

k=4

-2

3

-1

-4

5

61585 0

-58

v5

v2

v3

4

7v4

1v1

2

7-4

2-5

2 -5

4

v1 v2

v3

v5

v4

7-4

v1

v2

v3

v4

v5

2

4

-46

-58

3

7

1

0-5-124

50473

1-4032

4-1301

4321

k=4

-2

3

-1

-4

5

61585 0

v2

v1

v33

v5

-4 v4

1-5

2v5

v2

v3

4

v4

1v1

2-4

0-5-124

50473

1-4032

2-3101

4321

k=5

-2

3

-1

-4

5

61585 0

43

6

1

v1 v2

v3

v4

v5

v1v4

v56

v2

v3

2 -5

4

v4

v56

v1

v2

v3

v2

v5

-4

v1

v3

v4

2-5

4

v3

v2

v4

v5

1v12

-5

-4


• Una volta che abbiamo calcolato la matrice delle distanze minime D = D(n), come pos-siamo ricostruire i percorsi minimi ?

• In altre parole come possiamo calcolare la matrice dei predecessori P = P(n) ?

• Si possono usare essenzialmente due metodi:• Calcolare una sequenza di matrici dei predecessori

P(k) per k=1,…,n mentre calcoliamo D(k)

• Calcolare P direttamente da D (Esercizio 26-1.5)

Esercizio Trovare il percorso minimo da b ad ogni altro vertice c 4 2 14 3 4 4 ef d b a 5 1 1 04 2...

Documents

Transcript of Esercizio Trovare il percorso minimo da b ad ogni altro vertice c 4 2 14 3 4 4 ef d b a 5 1 1 04 2...