Esercizio 5.2.5

0 passi visti su 3

Consegna

Con riferimento al grafo orientato G=(V,A)G = (V, A) della Figura 5.2 della dispensa (lo stesso dell'Esercizio 5.2.3):

  1. si determini l'albero dei cammini minimi a partire dal nodo 7;
  2. si calcolino i cammini minimi da tutti i nodi a tutti i nodi.
Apri in Dijkstra Apri in Floyd-Warshall
0Dijkstra dal nodo 7apri
It.Esce1234567
0inizio[+∞, 0][+∞, 0][+∞, 0][+∞, 0][+∞, 0][+∞, 0][0, 7]
17[1, 7][+∞, 0][+∞, 0][1, 7][+∞, 0][+∞, 0][0, 7]
21[1, 7][2, 1][+∞, 0][1, 7][+∞, 0][+∞, 0]·
34·[2, 1][+∞, 0][1, 7][4, 4][+∞, 0]·
42·[2, 1][7, 2]·[4, 4][6, 2]·
55··[7, 2]·[4, 4][6, 2]·
66··[7, 2]··[6, 2]·
73··[7, 2]····

Alla seconda iterazione 1 e 4 sono alla pari con L=1L = 1 ed esce 1.

1Albero dei cammini minimiapri

L=(1,2,7,1,4,6,0)L = (1, 2, 7, 1, 4, 6, 0) e p=(7,1,2,7,4,2,7)p = (7, 1, 2, 7, 4, 2, 7). L'albero ha gli archi (7,1), (7,4), (1,2), (2,3), (2,6), (4,5).

2Tutte le coppieapri

Il grafo è quello dell'Esercizio 5.2.3: le matrici di Floyd-Warshall sono le stesse, e la riga 7 di cc, (1,2,7,1,4,6,0)(1, 2, 7, 1, 4, 6, 0), coincide con le etichette di Dijkstra.