Bonjour à toutes et à tous,
J'ai à effectuer ce projet dont voilà l'énoncé complet :
1. Objectif du projet
Le but du projet est de visualiser graphiquement le plus court chemin entre deux sommets d'un graphe suivant deux critères différents.
Le graphe utilisé est une partie des routes entre une quarantaine de villes françaises.
Les deux critères considérés seront :
- la distance entre villes.
- le temps de parcours entre villes.
Le projet sera constitué de deux parties :
- une partie algorithmique portant sur la construction et l'exploitation d'un graphe.
- une partie graphique permettant de visualiser les résultats de la partie algorithmique.
Ces deux parties seront réalisées indépendamment pour permettre l'utilisation de la partie algorithmique seule.
La réalisation sera une application Java.
A la fin de la semaine, vous devez rendre :
- un rapport complet détaillant la mise en oeuvre du projet : fonctionnalités réalisées, modèle objet, descriptions des classes et méthodes.
- le code complet du projet.
2. Partie algorithmique
Le but final est de déterminer le plus court chemin entre deux points. Le travail demandé se compose de plusieurs étapes :
- constitution du graphe à partir du fichier texte "routes.txt" .
- calcul du plus court chemin entre un sommet et les autres sommets du graphe par l'algorithme de Dijkstra suivant un des deux critères énoncés ci-dessus.
- sélection du plus court chemin demandé parmi l'ensemble de résultats de la phase précédente,.
2.1. Constitution du graphe
Le but de cette étape est de construire le graphe à partir d'un fichier texte en utilisant une représentation par listes d'adjacence.
Le graphe initial est donné dans le fichier "routes.txt".
Le fichier décrit le graphe de la façon suivante :
- première ligne : liste des sommets du graphe. Cette liste est constituée d'une suite de trigrammes (trois lettres) représentant chacun une ville. La signification de chaque trigramme est donné dans le fichier "villes.txt". La fin de liste est signifiée par un point virgule.
- lignes suivantes : le premier trigramme est un sommet du graphe. Ceux qui suivent (derrière les deux points) sont les successeurs du premier trigramme.
Exemple : Les successeurs de AMI (Amiens) sont : LIL (Lille ), REI (Reims), CAL (Calais) et ROU (Rouen).
Les deux nombres qui suivent chaque successeur seront les critères utilisés pour le calcul du plus court chemin :
- premier nombre : distance entre les villes.
Exemples : distance entre Amiens et Lille : 116 km; distance entre Amiens et Reims : 170 km.
- deuxième nombre : vitesse maximale autorisée sur la route.
La fin de la liste des successeurs est signifiée par un point virgule.
Exemple : vitesse sur la route entre Amiens et Lille : 90 km/h.
Ces deux informations seront portées sur chaque arête.
L'ajout d'autres villes dans le fichier ne doit en aucun cas modifier le code de cette partie.
2.2. Calcul des plus courts chemins
Une fois le graphe construit, cette étape consiste à calculer les plus courts chemins à partir d'un sommet donné par l'utilisateur. L'algorithme utilisé sera celui de Dijkstra.
L'algorithme devra prendre en paramètre le critère utilisé pour le calcul dont la valeur sera :
- soit "distance" : pour calculer le chemin de plus courte distance.
- soit "temps" : pour calculer le chemin de plus faible temps de parcours (les tronçons sont supposés être parcourus à vitesse la maximale autorisée).
Rappel sur l'algorithme :
Il consiste à trouver tous les plus courts chemins pour aller d'un sommet donné vers tous les autres.
On entend par "plus court chemin" , le chemin dont la somme des coûts des arcs est minimal.
On construit les plus courts chemins par étape.
On utilisera pour l'algorithme deux tableaux :
- l'un contenant le coût des plus courts chemins à chaque étape . C[i] est la valeur du plus court chemin du sommet initial au sommet i.
- l'autre contenant le sommet de l'avant dernière étape en prenant le chemin le plus court . S[i] contient le sommet d'où on vient pour arriver à i.
2.3. Exploitation des résultats
Les données entrées par l'utilisateur seront une ville de départ et une ville d'arrivée.
L'étape précédente donne tous les plus courts chemins entre la ville de départ et les autre villes du graphe.
Cette étape va consister à sélectionner le plus court chemin demandé parmi les résultats précédents et renvoyer le résultat devant contenir :
- la distance totale ou le temps de parcours total.
- la liste des villes intervenant dans le plus court chemin.
En option, on pourra ajouter une fonction permettant de calculer le temps de parcours et la distance pour un chemin donné.
3. Partie graphique
3.1. Présentation générale
La partie graphique de l'application sera réalisée avec le package Swing de la bibliothèque Java.
Au lancement, l’interface devra présenter les éléments graphiques suivants :
- une carte de France contenant les villes du fichier correctement disposées, et les différentes routes existant entre les villes (on prendra des couleurs différentes en fonction du type de la route)
- un composant permettant le choix d’une ville arrivée et une ville destination (on peut également sélectionner un ville en cliquant dessus),
- un composant permettant de choisir le critère du plus court chemin,
- un bouton lançant l’algorithme du plus chemin avec les paramètres d’entrée choisis.
Les résultats seront présentés suivant deux formes :
- le trajet calculé sera visualisé sur la carte avec une couleur différente de celles des routes.
- Un composant (JtextField par exemple) donnera les résultats du calcul du plus court chemin calculé :
- distance totale à parcourir,
- temps total du parcours
- villes intermédiaires.
Mon code est disponible dans la rubrique programmation, dans un dossier intitulé A L'AIDE !!! Projet Java
je suis bloqué, quelqu'un pourrait-il m'aider ?
Merci d'avance
![[:zzzinv]](/static/images/perso/zzzinv.gif "[:zzzinv]")
| Mes ventes! 
