le plus court chemin ... ? Fermé

Question

Bonjour, 

je cherche une algorithme qui cherche le plus court chemin j'ai vue l'algorithme de dijkstra mais je n'arrive pas a l'implémenté en C ... du au faite que quand je tombe dans le cas suivant 

par exemple : de A ---> B (40km) et de B ---> D (100km)
                      de A ---> C (100km) et de C ---> D (20km)

suivant l'algorithme de dijkstra si on est à A et on veux allé vers D le programme vas faire le suivant :
1) choisir de A --> B car elle est la plus court 
2) continué de B --> D 

et c'est pas le plus court chemin ... !!!

donc comment résoudre se problème et est ce que j'ai bien compris l'algorithme de dijkstra ??

et merci d'avance

sambia39 · Answer

Bonsoir 
Tu as plus ou moins compris le principe mais ceci dit dans cet algorithme tu dois toujours partir du chemin minimal donc dans ton exemple cela donnerais :

A -> B = (0+40) = 40A -> C = (0+100) = 100 [A traité] B -> D = (40+100) = 140 [B traité]C -> D = (100+20) = 120 [C traité]donc logiquement le chemin le plus court est A -> C -> D = 120  
à bientôt

Le plus court chemin ... ?

1 réponse

Discussions similaires