Esercizio 5.2.3

0 passi visti su 3

Consegna

Con riferimento al grafo orientato G=(V,A)G = (V, A) della Figura 5.2 della dispensa, con archi (1,2) 1, (1,4) 5, (2,3) 5, (2,4) 1, (2,5) 6, (2,6) 4, (3,6) 2, (4,5) 3, (5,3) 9, (5,7) 1, (6,1) 3, (7,1) 1, (7,4) 1:

  1. si determini l'albero dei cammini minimi a partire dal nodo 1;
  2. si calcolino i cammini minimi da tutti i nodi a tutti i nodi.
Apri in Dijkstra Apri in Floyd-Warshall
0Dijkstra dal nodo 1apri

I costi sono non negativi. Etichette [L,p][L, p]; il punto · indica un nodo già definitivo.

It.Esce1234567
0inizio[0, 1][+∞, 0][+∞, 0][+∞, 0][+∞, 0][+∞, 0][+∞, 0]
11[0, 1][1, 1][+∞, 0][5, 1][+∞, 0][+∞, 0][+∞, 0]
22·[1, 1][6, 2][2, 2][7, 2][5, 2][+∞, 0]
34··[6, 2][2, 2][5, 4][5, 2][+∞, 0]
45··[6, 2]·[5, 4][5, 2][6, 5]
56··[6, 2]··[5, 2][6, 5]
63··[6, 2]···[6, 5]
77······[6, 5]

Alla quarta iterazione 5 e 6 sono alla pari con L=5L = 5 ed esce 5, di indice minore.

1Albero dei cammini minimiapri

Gli archi (pv,v)(p_v, v) formano l'albero: (1,2), (2,3), (2,4), (2,6), (4,5), (5,7).

2Floyd-Warshallapri

Alla prima iterazione, h=1h = 1, da 6 a 2 non c'è un arco ma passando per 1 si spende c[6,1]+c[1,2]=3+1=4c[6,1] + c[1,2] = 3 + 1 = 4: c[6,2]:=4c[6,2] := 4 e p[6,2]:=p[1,2]=1p[6,2] := p[1,2] = 1. Dopo le sette iterazioni:

cc1234567
10162556
26051445
3560710211
4561103104
52382071
63495809
71271460
pp1234567
11122425
27222425
36132435
47124425
57127525
66122465
77127427

Il cammino da 3 a 5 si legge sulla riga 3 di pp: p[3,5]=4p[3,5] = 4, p[3,4]=2p[3,4] = 2, p[3,2]=1p[3,2] = 1, p[3,1]=6p[3,1] = 6, p[3,6]=3p[3,6] = 3, cioè 3 → 6 → 1 → 2 → 4 → 5, con costo 10. La riga 1 coincide con Dijkstra.