Collaborateurs

• Wu Mei-ling (@Mei-lingWu)
• Graindorge Adam (@Issuko-Adam)
• Grajezyk Nathan (@NathanGRK)
• Boutebakh Elias (@Elias951)

Chargé de TP

• MR. Foughali(@kf-iut)

Partie I

• LArc

  • On représente un graphe en stockant une liste d'arcs qui contiennent leurs sources, destinations et valuations.

• LAdj

  • Chaque sommet est associé à une liste de ses successeurs. Donc pour tout sommet ou il y a un arc sortant.

• HHAdj

  • On représente un graphe grâce à une hashmap d'hashmaps. Chaque sommet possède une map contenant les successeurs du sommet et leurs valuations.

Partie II

Nous avons implémenté et validé les tests suivants pour l'algorithme Djikstra, en fonction des différents types de graphes :

Dossier "Autres"

• MAdj
• HHAdj
• LAdj
• LArc

Dossier "Orig" (en entier)

• HHAdj
• LAdj

Dossier "Orig" (taille < 10 000)

• MAdj : Trop long

Dossier "Orig" (taille < 100 000)

• LArc : Trop long

Dossier "Barabasi" (en entier)

• HHAdj
• LAdj

Dossier "Barabasi" (taille < 10 002)

• MAdj

Dossier "Barabasi" (taille < 100 002)

• LArcs

Dossier "Full"

• LAdj
• HHAdj
• MAdj

Dossier "Full" (taille < 501)

• LArc

Architecture

Performances

• performance.pdf