Grafo aciclico nodo con distanza minore da tutti

[gaiapuffo]

Salve,ho un progetto di algoritmi. Mi interessa ottimizzare solo una parte,praticamente ho un grafo aciclico,archi non orientati,devo trovare il nodo la cui distanza è minima rispetto a tutti gli altri nodi. Ossia il nodo che raggiunge tutti gli altri con la distanza minore. Ad esempio se ho

2-4-3-1 ho che 4 ha distanza 2 mentre 1 ha distanza 3 quindi 4 e più vicino a tutti i nodi. Stessa cosa 2 ha 3 e 3 ha 2 quindi si può dire che il nodo la cui distanza e minima dagli altri nodi sono 4 e 3. Spero di essere stato chiaro, Un metodo e prendere tutti i nodi e per ognuno calcolare l'erdos,ma è poco efficiente. Sapete un algoritmo,mi postate un link o me lo spiegate?

[hamming_burst]

stesso progetto?

[gaiapuffo]

già compagno di corso quindi:) ho fatto l'algoritmo ma ho preso 25% perchè è troppo lento,quindi una soluzione di ottimizzazione e nella ricerca del percorso minimo. Io sono ad esempio in gruppo da solo,causa vari motivi e non può passare da problemi di difficoltà 2 o 3,a problemi di difficoltà 100....

[apatriarca]

Potresti limitarti a calcolare la distanza rispetto ai solo nodi "terminali" (quelli che sono collegati al grafo attraverso un solo arco). Non essendoci cicli i nodi di massima distanza devono per forza trovarsi tra questi.