2009-12-03 – 12

Il grafo dei collegamenti bidirezionali fra 7 nodi (n1, n2, …, n7) è descritto da una tabella

Trovare la lista L del percorso più breve dal nodo n1 al nodo n7 e calcolarne la distanza D in chilometri.

Soluzione: L=[n1, n2, n5, n7], D=365.


Disegno il grafo corrispondente alla tabella e individuo la soluzione passo-passo

2009_10_lm_12_1

Distanze minime tra n1 e le città immediatamente vicine (n2 e n4)

n1 -> n2 = 140
n1 -> n4 = 120
2009_10_lm_12_2
Distanze minime tra n1 e le città immediatamente vicine a n2 e n4 (n3, n5, n6)

n1 -> n2 = 140
n1 -> n2 -> n3= 320
n1 -> n4 = 120
n1 -> n2 -> n4= 240, scartata
n1 -> n2 -> n5= 205
n1 -> n4 -> n5= 290, scartata
n1 -> n4 -> n6 = 350

2009_10_lm_12_3

Distanza minima tra n1 e la città immediatamente vicina a n3, n5, n6 (n7)

n1 -> n2 = 140
n1 -> n2 -> n3= 320
n1 -> n4 = 120
n1 -> n2 -> n5= 205
n1 -> n4 -> n6 = 350
n1 -> n2 -> n5 -> n7 = 365
n1 -> n2 -> n3 -> n7 = 470, scartata
n1 -> n4 -> n6 -> n7 = 440, scartata

2009_10_lm_12_4

I grafi illustrano i passaggi risolutivi ma sono superflui rispetto ai calcoli algebrici.