[Résolu][C] Mathématiques: implémentation de l'algorithme de Dijkstra.
Forum Programmation : [Résolu][C] Mathématiques: implémentation de l'algorithme de Dijkstra.
Voila, jai donc un problème: je dois implémenter l'algorithme de Dijkstra (recherche du plus court chemin dans un graphe) en C. J'aurais donc besoin d'aide; plus particulièrement sur la ligne 9... (En gros, sa signification, comment coder ca en C...)
Je peux aussi mettre le code de ce que j'ai déja fait (et qui ne marche pas, malheureusement), si ca peut "aider quelqu'un à m'aider" ;-) .
Voila, et merci d'avance.
Edit:J'ai finalement résolu le problème... Je posterais peut etre le code source de mon algorithme si j'ai rien d'autre a faire. Ou si quelqu'un me le demande en mp.
Ah, et puis merci tiopai.
Message édité par Rakipu le 15-02-2007 à 06:50:02
Dikstra... mon algo préfèré pour les plus courts chemins...
En fait la ligne 9 consiste à sélectionner le sommet de S bar de valeur minimum. Ensuite on met ce sommet x_i dans S ce qui veut dire que l'on connait définitivement la valeur de son plus court chemin entre x_0 et x_i. En effet, l'algorithme fonctionne lorsque les arcs (ou arêtes) ne sont valués que par des nombres positifs, ce qui permet de choisir a chaque étape le sommet non traité dont la valeur est la plus petite et de placer ce sommet dans S qui correspond a l'ensemble des sommets dont nous connaissons le plus court chemin à partir de x_0...
J'espère que j'ai été claire... (hum j'en suis pas si sur 
)
