Problème du voyageur (heuristique du plus proche voisin)

Villes $\{1,2,3,4,5\}$, distances : $d(1,2)=10$, $d(1,3)=15$, $d(1,4)=20$, $d(1,5)=25$, $d(2,3)=35$, $d(2,4)=25$, $d(2,5)=30$, $d(3,4)=30$, $d(3,5)=20$, $d(4,5)=15$.

Appliquer l'heuristique du plus proche voisin depuis 1. Calculer le coût.