En fait pour calculer le plus cours chemin ce n'est pas très difficile avec
ton énoncé.

Tu ajoutes à ton objet Carte un membre Itinéraire que tu instancie par défaut dont la signature est:

public class Itineraire {
  Ville mVilleDepart;
  Ville mVilleArrivee;
  List<Ville> mVillesParcourues;

  public Itineraire() {
    mVillesParcourues = new ArrayList<Ville>();
  }
    
  public Itineraire(Ville pVilleDepart, Ville pVilleArrivee) { 
    mVilleDepart = pVilleDepart;
    mVilleArrivee = pVilleArrivee;
    mVillesParcourues = new ArrayList<Ville>(); 
  } 
 
  public void calculeItineraire();

  public void getVilleDepart();

  public void getVilleArrivee();

  public void getVillesParcourues();

  public void setVilleDepart(Ville villeDepart);
	
  public void setVilleArrivee(Ville villeArrivee);
	
  public void setVillesParcourues(List<Ville> villesParcourues);

et fait référence au morceau de code que je t'ai passé qqes posts avant.
NB : Revoir le code de la méthode calculeDistance() je crains qu'il soit érroné.

Tu ajoutes a ton objet Carte une methode :

private void dessineItineraire(Graphics g) {
    	g.setColor(Color.blue);
    	
    	if (mItineraire.getVilleDepart() != null) {
    		g.drawString(
    				mItineraire.getVilleDepart().getNom(), 
    				mItineraire.getVilleDepart().getCoordonnees().x - 12, 
    				mItineraire.getVilleDepart().getCoordonnees().y - 2); 
        	g.fillRect(
        			mItineraire.getVilleDepart().getCoordonnees().x, 
        			mItineraire.getVilleDepart().getCoordonnees().y, 
        			2, 
        			2); 
    	}
    	
    	if (mItineraire.getVilleArrivee() != null) {
    		g.drawString(
    				mItineraire.getVilleArrivee().getNom(), 
    				mItineraire.getVilleArrivee().getCoordonnees().x  - 12, 
    				mItineraire.getVilleArrivee().getCoordonnees().y  - 2); 
        	g.fillRect(
        			mItineraire.getVilleArrivee().getCoordonnees().x, 
        			mItineraire.getVilleArrivee().getCoordonnees().y, 
        			2, 
        			2); 
    	}
    	
    	for (int i = 0; i < mItineraire.getVillesParcourues().size() - 1; i++) {
    		g.drawLine(
    				mItineraire.getVillesParcourues().get(i).getCoordonnees().x, 
    				mItineraire.getVillesParcourues().get(i).getCoordonnees().y, 
    				mItineraire.getVillesParcourues().get(i + 1).getCoordonnees().x, 
    				mItineraire.getVillesParcourues().get(i + 1).getCoordonnees().y);
    	}
    }

Des que tu sélectionnes une ville dans ton comboBox :
- deux cas de figure :
1 c est le comboBox ville de depart
2 c est le comboBox ville d arrivee

  public void itemStateChanged(ItemEvent e) {
		if (e.getSource().equals(mComboBoxVilleDepart)) {
			pcentre.getItineraire().setVilleDepart(#LaVilleSelectionnee#);
		} else if (e.getSource().equals(mComboBoxVilleArrivee)) {
			pcentre.getItineraire().setVilleArrivee(#LaVilleSelectionnee#);
		}
				
		pcentre.updateUi();
	}

Pour finir dès que tu appuies sur le bouton qui permet de lancer le calcul
de l itineraire tu fais :

  public void actionPerformed(ActionEvent e) {
    pcentre.getItineraire().calculeItineraire();
  }

Bonne chance,
Niroken