Algorithme de recherche du plus court chemin
Description du projet
Ce projet universitaire m'a permis d'approfondir mes connaissances en algorithmique et structure de données. L'objectif était d'implémenter et comparer plusieurs algorithmes de recherche du plus court chemin entre différents points dans un graphe, codés entièrement en Python.
Objectifs
- Implémenter trois algorithmes majeurs de plus court chemin
- Comprendre les concepts de graphes et de recherche de chemins
- Analyser et comparer les performances des algorithmes
- Créer une visualisation des résultats
- Optimiser le code pour différents types de données
Algorithmes implémentés
Dijkstra
Algorithme glouton trouvant le chemin le plus court depuis un sommet source vers tous les autres sommets, adapté aux graphes à poids positifs.
A*
Algorithme de recherche heuristique combinant les avantages de Dijkstra avec une heuristique pour accélérer la recherche.
Bellman-Ford
Algorithme capable de gérer les arêtes à poids négatifs, plus lent que Dijkstra mais plus flexible.
Technologies utilisées
Points forts
- Implémentation complète et correcte de trois algorithmes complexes
- Gestion efficace des structures de données (listes, dictionnaires, priorités)
- Analyse comparative des algorithmes (complexité temporelle et spatiale)
- Visualisation graphique des résultats
- Code testé et validé
Apprentissages
Ce projet m'a permis de maîtriser les concepts fondamentaux d'algorithmique et de structure de données. J'ai appris à implémenter des algorithmes complexes, à analyser leur performance, et à traiter des graphes. C'est un excellent projet pour démontrer la compréhension des algorithmes classiques en informatique.
Résultats
- Les trois algorithmes produisent les mêmes chemins optimaux
- Dijkstra et A* sont plus performants que Bellman-Ford sur les graphes sans poids négatifs
- A* offre la meilleure performance en utilisant une heuristique appropriée
- Bellman-Ford gère correctement les cas limites