Version imprimable
J'ai un projet d'étude à faire qui consiste à modéliser la structure d'un réseau de transport d'une ville et de rechercher le PCC entre plusieurs stations.
J'ai choisi d'utiliser des listes chaînées pour représenter le réseau. Je pense que le réseau comportera une centaine de station.
Maintenant je réfléchis à l'algorithme à mettre en place pour la recherche des PCC. J'ai le choix entre :
- Floyd
- Bellman
- Dijstra
Pourrez-vous me dire dans quel cas utiliser quel algo ?
D'avance, merci
Etant donné qu'il s'agit d'un réseau de transport, la solution la plus efficace sera surement Dijkstra. Floyd s'éxécutant en n^3 ça ne devait pas être une bonne idée, sans compter l'espace nécéssaire à l'algorithme.
Cependant, si le nombre de PCC est grand, il est peut-être envisageable d'utiliser Floyd.
Mais je ne vois pas en quoi Bellman pourrait être justifié.
Je n'arrive pas à mettre la main sur la complexité spaciale de Dijkstra et d'autres algo (Floyd-Warshall, Bellman, Fords-Fulkerson et MKM).
Parceque qu'au niveau de la complexité temporelle, c'est bien Dijkstra qui semble l'emporter de loin, mais au niveau de la complexité spaciale je ne trouve rien ...
Sans compter le stockage du graphe:
Pour Floyd (ou Roy-Warshall, ou Roy-Floyd, ou encore Floyd-Warshall...), tu as besoin d'une matrice pour stocker le plus court chemin entre chaque paires de points, donc N^2 en mémoire.
Pour Dijkstra t'as un tas qui contient au max N élements (les noeuds ainsi que la distance au départ). Par contre uniquement si tu peux mettre à jour un élément dedans, sinon tu replaces à chaque fois et tu montes aussi à N^2.
Pour Bellman-Ford tu dois stocker la distance entre le départ et chaque noeud, donc en N.
Bellman est utile pour traiter le cas d'arcs à valuation négative. Dijkstra est le plus simple à utiliser mais il ne te donne le pcc vers les autres ommets de ton graphe pour un seul point donné.
Floyd te permet de calculer un dsitancier car il fait le travail du calcil des pcc pour tous les sommets de ton graphe. C'est "comme si" tu utilisais Dijkstra "en boucle". Mais Floyd est le plus adapté pour un distancier.