import java.util.HashMap;

/** Tables des plus courtes longueurs entre les villes, la valeur est null si il n'y a pas de chemin. */
HashMap<StringPair, Double> Longueurs = new HashMap<StringPair, Double>();

/** Renvoie la longueur du chemin de la ville de départ à la ville d'arrivée, ou MAX_VALUE si il y a pas de chemin. */
double getPathDistance(String depart, String arrivee) {
  Double l = Longueurs.get(new StringPair(depart, arrivee));
  return l == null ? Double.MAX_VALUE : l;
}
/** Tables de routage qui donne la ville suivante du plus court chemin entre deux villes, la valeur est null si il n'y a pas de chemin. */
HashMap<StringPair, String> Routage = new HashMap<StringPair, String>();

/** Renvoie la ville suivante sur le chemin de la ville de départ à la ville d'arrivée, ou null si il y a pas de chemin. */
String getPathNextNode(String depart, String arrivee) {
  String n = Routage.get(new StringPair(depart, arrivee));
  return n == null || voisins.get(depart).contains(n|| n.equals(arrivee? n : getPathNextNode(depart, n);
}
// Calcule la table des chemins les plus courts.
{
  // Initialise la table avec les chemins de longueurs zéro et un.
  for(String ville : villes) {
	Longueurs.put(new StringPair(ville, ville)0.0);
	Routage.put(new StringPair(ville, ville), ville);
	for(String voisin : voisins.get(ville)) {
	  Longueurs.put(new StringPair(ville, voisin), getDistance(ville, voisin));
	  Routage.put(new StringPair(ville, voisin), voisin);
	}
  }
  // Calcule ensuite itérativement les chemins de longueur supérieure à un.
  //
  //
  //
  // Oh zut !! Cette partie du code est manquante . . qui saura la compléter ???
  //
  //
  //
}

// Test de l'algorithme contre la méthode de la proglet.
void test() {
  for(String depart : villes)
	for(String arrivee : villes) {
	  String ville = depart;
	  for(String etape : plusCourtCheminGogleMap(depart, arrivee)) {
		if(!etape.equals(ville)) {
		  println(" AH ! Il y a un bug dans l'algorithme de Roy_Floyd_Warshall");
		}
		ville = getPathNextNode(ville, arrivee);
	  }
	  print(".");
	}
  println("\nOK");
}
void main() {
  test();
}