Le plus court chemin ... ?

gacki Messages postés 109 Date d'inscription   Statut Membre Dernière intervention   -  
sambia39 Messages postés 610 Date d'inscription   Statut Membre Dernière intervention   -
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

1 réponse

Réponse 1 / 1
sambia39 Messages postés 610 Date d'inscription   Statut Membre Dernière intervention   49
 
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
0

Discussions similaires

court circuit LNB " apparaît.
Yasmine -
Anonyme -

2 réponses
Chemin Logo du site de la Cité de l'espace
Keiios -
blux -

11 réponses
3 bip long 2 bip courts
bgielel -
Bgiebgielel -

14 réponses
Court circuit LNB
adeline -
Lechatauxgrosyeux -

9 réponses
surcharge du circuit LNB
alain -
Andy31200 -

1 réponse