Les algorithmes de calcul deplus court chemin
Résolu
Bonjour, S V P est ce que qlq'un peut m'aider , j'ai besoin d'une article qui fait la comparaison entre les algorithmes de plus court chemin ( Algorithme Dijkstra , Ford-Bellman , A*,Floyd-Warshall ,Kruskal ) ou au moins les inconvénients de ces algorithmes sauf Dijkstra.
et merci pour vous :)
et merci pour vous :)
Configuration: Windows XP Firefox 3.0.10
5 réponses
-
-
Tu peux regarder les implémentations de ces algorithmes sur wikipedia et sur libboost. Tu verras qu'en terme de complexité Dijsktra est le plus efficace (c'est celui qui est utilisé dans les routeurs qui implémentent le protocole OSPF ou IS-IS).
https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
https://fr.wikipedia.org/wiki/Algorithme_de_Ford-Bellman
...
https://www.boost.org/doc/libs/1_46_1/libs/graph/doc/table_of_contents.html
https://www.boost.org/doc/libs/1_46_1/libs/graph/doc/dijkstra_shortest_paths.html
https://www.boost.org/doc/libs/1_46_1/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html
...
Je t'invite à lire également la généralisation de ces algorithmes dans cet excellent bouquin :
http://www.lavoisier.fr/livre/notice.asp?id=3LKW2OAOKS6OWL
C'est le bouquin qe devrait lire toutes les personnes qui font de la théorie des graphes à mon humble avis ;-)
Bonne chance -
-
-
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question -
De rien :-)
