Io l'ho fatto e credo sia giusto.
Ho fatto per ogni nodo(A) del grafo e per ogni nodo(B) a cui A si collegava: la distanza minima tra B e gli altri nodi a cui A si collegava non passando ovviamente per A.
poi ho preso la minima somma tra AB+percorsoMinimo(C)+AC.