le domande che ti ho fatto sono utili per sapere il tipo di soluzione che cerchi

purtroppo non ho tempo per risolvere l'esercizio, (prometto che se in pausa pranzo mi avanzano 5 min, gli do un'occhiata)

cmq, se ti può essere utite c'è un certo signor Dijkstra (letto daistrà) che ha fatto qualche studio su questo tipo di problemi, ti posto il link wiki

http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra

puoi fare una ricerca su goolge scrivendo "cammino minimo su grafo"