SAE 2.02 : Graphes Orientés Valués

Manipulation de graphes. Projet de 4 élèves du groupe 103.
Chargé de TP : Camille KURTZ
Le SDK utilisé est OpenJDK 19. Notre projet est donc écrit pour fonctionner avec Java 19, et pourrait donc ne pas fonctionner sur d'autres versions de Java

Auteurs

• Eva G.
• Rémi L.
• Ali K.
• Mya F.

Synthèse du travail

Partie 1 : Représentation des graphes orientés valués

Nous nous sommes conjointement répartis les différents types de graphe à implémenter.

• Ali se charge des graphes représentés par une table de hachage (GrapheHHAdj.java).
• Rémi se charge des graphes représentés par une liste d'adjacence (GrapheLAdj.java).
• Eva se charge des graphes représentés par une matrice d'adjacence (GrapheMAdj.java).
• Mya se charge des graphes représentés par une liste d'arcs (GrapheLArcs.java).

Les 4 classes ont été codées et fonctionnent.

Partie 2 : Algorithme du plus court chemin de Dijkstra

Notre implémentation de l'algorithme de Dijkstra passe les tests jusqu'à différents niveaux en fonction des types de graphes :

• GrapheHHAdj : Tous les graphes passent les tests (jusqu'à 1000000-1 inclus).
• GrapheLAdj : jusqu'à 100000-1 inclus.
• GrapheLArcs : jusqu'à 10000-1 inclus.
• GrapheMAdj : jusqu'à 10000-1 inclus.

Tests unitaires

Nous avons programmé différents tests unitaires, ils sont disponibles dans le paquetage testspersos.

Tests de performance

Les résultats des tests peuvent être trouvés sur le fichier perfs.md.

Crédits

• Keith Schwartz pour l'implémentation du tas de Fibonacci. Son code a été modifié dans le projet (remplacement des double par des int)