Jump to content

Algorithme des graphes


Recommended Posts

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 :

  1. 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 ?
  2. 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

Link to comment
Share on other sites

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 :ouioui:

Link to comment
Share on other sites

Archived

This topic is now archived and is closed to further replies.

×
×
  • Create New...