Sarvok Posté(e) le 16 mai 2007 Partager Posté(e) le 16 mai 2007 Hello, Mon école me demande de faire un projet assez courant : on a un réseau de transport d'une ville et il faut trouver le plus cours chemin à partir des arrêts fournis par l'utilisateurs. J'aurais quelques questions : Déjà pour la réprésentation du graphe, on me propose de le faire soit en liste, soit en matrice. Je crois que pour un réseau fortement connexe il vaut mieux utiliser les matrices et pour les réseaux faiblement connexes, utiliser les listes ? D'autres facteurs sont à prendre en considération pour le choix d'une ou d'une autre représentation ? Ensuite pour l'algorithme du plus cours chemin, je peux utiliser Floyd, Bellman ou Dijkstra. La différence s'effectue au niveau de la complexité temporelle/spaciale ? Est-ce que, selon la connexité, il vaut mieux en utiliser un en particulier ? D'avance, merci Lien vers le commentaire Partager sur d’autres sites More sharing options...
beuhbeuh Posté(e) le 16 mai 2007 Partager Posté(e) le 16 mai 2007 Pour ce qui est de la représentation, tu as tout bon. L'autre facteur est la complexité du code. Travailler avec les matrices est plus compliqué qu'avec des listes. Pour l'algo à utiliser, la complexité ne dépend pas de la connexité (si ma mémoire est bonne) mais de la taille de ton graphe (nombre de noeuds)... Dijkstra reste le plus facile à implémenter Lien vers le commentaire Partager sur d’autres sites More sharing options...
Messages recommandés
Archivé
Ce sujet est désormais archivé et ne peut plus recevoir de nouvelles réponses.