Bonjour,
Par rapport à ton énoncé :

et les premiers éléments donnés pour construire la classe itinéraire, je te propose ceci :

import java.util.ArrayList;
import java.util.List;

public class Itineraire {
    Ville mVilleDepart;
    Ville mVilleArrivee;
    List mVillesParcourues;
    
    public Itineraire(Ville pVilleDepart, Ville pVilleArrivee) {
        mVilleDepart = pVilleDepart;
        mVilleArrivee = pVilleArrivee;
        mVillesParcourues = new ArrayList();
    }
    
    public void calculeItineraire() {
        mVillesParcourues.add(mVilleDepart);
        Ville vVilleSuivanteTmp = mVilleDepart;
        
        while (!(vVilleSuivanteTmp = getVilleLaPlusProcheDeVilleArrivee(vVilleSuivanteTmp.mVillesVoisines)).equals(mVilleArrivee)) {
            mVillesParcourues.add(vVilleSuivanteTmp);
        }
        
        mVillesParcourues.add(mVilleArrivee);
    }
    
    public Ville getVilleLaPlusProcheDeVilleArrivee(Ville[] pVillesVoisines) {
        Ville vResult = pVillesVoisines[0];
        
        for (int i = 0; i < pVillesVoisines.length; i++) {
            if (vResult.getDistance(mVilleArrivee) < pVillesVoisines[i].getDistance(mVilleArrivee)) {
                vResult = pVillesVoisines[i];
            }
        }
        
        return vResult;
    }
}

class Ville {
    String mNom;
    Ville[] mVillesVoisines;
    int[] mDistancesVoisines;
    
    public int getDistance(Ville pVille) {
        return 0;
    }
    
    public boolean equals(Object pObject) {
        if (pObject instanceof Ville) {
            if (mNom != null && mNom.equals(((Ville) pObject).mNom)) {
                return true;
            }
        } 
        
        return false;
    }
}

Je n'ai pas testé ce bout de code, mais soyons confiants :D

Bonne chance,
Niroken