Le plus court chemin ... ?
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
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
1 réponse
-
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) = 40
A -> 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
