Cammini minimiAlgoritmo SPT.Acyclic

Esercizio 1 Sia dato il seguente grafo orientato aciclico, in cui i numeri accanto agli archi sono le lunghezze, e la radice r è il nodo di indice 1

1

6

2 3

4

51

1

1

7

1

1

3

4

Si determini l’ordinamento dei nodi trovato dalla procedura Aciclico.Si determini l’albero dei cammini minimi utilizzando l’algoritmo SPT.Acyclic.

Ordinamento trovato dalla procedura Aciclico

1

6

2 3

4

51

1

1

7

1

1

3

4

1

4

2

5

3

6

1

0

∞

∞

∞7

1

6

2 3

4

51

1

1

7

1

1

3

4

Iterazione 1: analisi nodo 1

1 2

3

4

5

6

1

0

2

∞

∞7

1

6

2 3

4

51

1

1

7

1

1

3

4

Iterazione 2: analisi nodo 6

1 2

3

4

5

6

1

0

2

6

53

1

6

2 3

4

51

1

1

7

1

1

3

4

Iterazione 3: analisi nodo 5

1 2

3

4

5

6

1

0

2

6

43

1

6

2 3

4

51

1

1

7

1

1

3

41 2

3

4

5

6

Iterazione 4: analisi nodo 2

1

0

2

5

43

1

6

2 3

4

51

1

1

7

1

1

3

41 2

3

4

5

6

Iterazione 5: analisi nodo 3

risultato finale

Nota: non si considera l’ultimo nodo dell’ordinamento (nodo 4) che non può precedere nessun nodo

Cammini minimiAlgoritmo SPT.Acyclic

Esercizio 2 Sia dato il seguente grafo orientato aciclico, in cui i numeri accanto agli archi sono le lunghezze, e la radice r è il nodo di indice 1

1

6

2 3

4

54

2

1

3

3

2

1

4

Si determini l’ordinamento dei nodi trovato dalla procedura Aciclico.Si determini l’albero dei cammini minimi utilizzando l’algoritmo SPT.Acyclic.

Ordinamento trovato dalla procedura Aciclico

1

6

2 3

4

54

2

1

3

3

2

1

4

5

6

4

1

2

3

0

∞

4

∞

∞

∞1

6

2 3

4

54

2

1

3

3

2

1

4

5

6

4

1

2

3

Iterazione 1: analisi nodo 1

0

∞

4

7

5

∞1

6

2 3

4

54

2

1

3

3

2

1

4

5

6

4

1

2

3

Iterazione 2: analisi nodo 6

Nota: si salta il primo nodo dell’ordinamento (nodo 2) che precede la radice e quindi non è ad essa connesso