Une activité sur l'algorithme du plus court chemin.

Objectif.

Le but de ce tutoriel est de comprendre l'algorithme du plus court chemin.

Apprendre à manipuler des tables associatives.

Un dictionnaire ou un répertoire téléphonique est une structure de donnée où une clé (le mot dont on cherche une définition ou le nom de la personne dont on cherche le numéro de télephone) est associée à une valeur. Celà diffère d'un tableau qui est uniquement indexé par des nombres entiers 0, 1, etc.
Il existe un objet Java, la HashMap qui implémente un tel container et il se manipule assez facilement:

// Déclaration de la structure de table associative

import java.util.HashMap;
../..
{

// Ici on construit une table (vide) qui associe à des String une valeur entière.

    HashMap<String,Integer> ages = new HashMap<String,Integer>();

// Ici on ajoute deux valeurs dans cette table.

    ages.put("Toto", 12);
    ages.put("Tata", 23);

// Ici on récupère une des valeurs (présentement 23).

    int a = ages.get("Tata");

// Ici on teste si une valeur existe parmi les clés de la table (présentement true pour b et false pour d).

    boolean b = ages.keySet().contains("Tata"), d = ages.keySet().contains("Titi");

// Ici on énumère toutes les clés de la table et imprime les valeurs correspondantets.

    for (String n : ages.keySet())
        println("Salut " + n + ", tu as " + ages.get(n) + " ans");
}
On utilise donc les fonctions:
À faire: En construisant une table des âges ou tout autre petite table de donnée se familiariser avec ces fonctions.

Présentation de l'algorithem.

L'algorithme de Roy-Warshall-Floyd est un algorithme très efficace pour calculer le plus court chemin entre toutes les paires de sommets d'un graphe. Calculant tous les plus courts chemins, cet algorithme détermine aussi s'il existe un chemin entre deux sommets ou non.
Plus précisément, cet algorithme calcule deux tableaux : un tableau L tel que L[x][y] soit la longueur du plus court chemin qui relie le sommet x et le sommet y et un tableau R tel que R[x][y] soit le premier successeur du sommet x qui permet de connaitre le plus court chemin menant vers le sommet y..
Au départ, on initialise le tableau L pour les chemins de longueur 0, L[x][x] prend la valeur 0 et pour les chemins de longueur 1 L[x][y] prend la valeur 1 s'il y a une arrête entre x et y et la valeur ∞ sinon. On initialise de même le tableau R : R[x][x]prend la valeur x, et R[x][y] prend la valeur y.
Ensuite on imbrique trois boucles : Pour tous les sommets intermédiaires z, Pour tous les sommets de départ x, Pour tous les sommets d'arrivée y, Si L[x][z] + L[z][y] < L[x][y] (c'est à dire si aller de x à y en passant par z est plus court que le plus court chemin connu) on remplace L[x][y] par L[x][z] + L[z][y] et R[x][y] par la valeur de R[x][z].On a donc stocké dans R[x][y] la valeur du successeur de x qui permet de connaitre, à ce stade, le plus court chemin vers le sommet y.

Etude de l'algorithme.

À vous : compléter l'algorithme de calcul du plus court chemin.

En utilisant la description de l'algorithme de Roy-Floyd-Warshall donné dans ce document utiliser le code proposé ici ici pour
Pour débugger le code, on pourra enrichir la routine test() de détails sur où l'algorithme a échoué.