OII 2011-12-02 – 18

2011_12_lm_11Il seguente grafo stradale:

può essere descritto dal seguente insieme di termini (ciascuno dei quali definisce un arco tra due nodi del grafo con la indicazione della relativa distanza)

a(n1,n2,2), a(n2,n3,5), a(n3,n4,3), a(n4,n5,4), a(n5,n6,2), a(n6,n1,3), a(n1,n7,8), a(n2,n7,6), a(n3,n7,1), a(n4,n7,9), a(n5,n7,7), a(n6,n7,4)

Un percorso tra due nodi del grafo può essere descritto con la lista dei nodi che lo compongono ordinati dal nodo di partenza al nodo di arrivo.

Per esempio, la lista [n5, n7, n2, n1] descrive un percorso dal nodo n5 al nodo n1 di lunghezza K = 15.

Dato il grafo stradale corrispondente al seguente insieme di termini:

a(n7,n2,2), a(n2,n3,6),,a(n2,n4,3), a(n9,n3,5), a(n7,n8,5), a(n3,n7,7), a(n4,n7,9), a(n1,n5,10), a(n8,n9,4), a(n6,n8,7), a(n5,n4,6), a(n5,n6,3), a(n6,n7,1), a(n3,n8,15), a(n1,n2,2)

Trovare la lista L del percorso più lungo fra il nodo n1 e il nodo n9 e calcolarne la lunghezza K.

N.B. Un percorso non può mai passare più di una volta da uno stesso nodo.


Soluzione: L=[n1, n5, n4, n7, n6, n8, n3, n9], K=53.


L’esempio del testo corrisponde alla figura

2011_12_18_e

La soluzione del quesito corrisponde al percorso blu in figura

2011_12_18