Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Algorithme de Dijsktra

Posté par
Allison
05-03-13 à 18:23

Bonjour,
J'essaie de réaliser l'algorithme de Dijsktra (trouver le chemin le plus court) pour une classe avec le logiciel Algobox.
Mais plusieurs problèmes se posent...
Tout d'abord, la boucle ''tant que'' que j'utilise dans l'algorithme s'arrête une fois sur trois alors que le programme est sensé être fini et je n'ai pas la moindre idée de la cause de ce problème.
Ensuite, pour certaines valeurs, le programme ne trouve aucune réponse et fait un "va et vient" entre deux valeurs sans s'arrêter. Je ne sais pas comment faire pour résoudre ce deuxième problème.
Merci par avance pour vos réponse !

Posté par
Glapion Moderateur
re : Algorithme de Dijsktra 05-03-13 à 21:30

Bonsoir, si tu nous donnais l'algorithme en question et plus clairement ce qu'il est censé donner comme résultat, ça serait plus facile de te répondre.

Posté par
Allison
re : Algorithme de Dijsktra 06-03-13 à 11:19

Bonjour,
Voici l'algorithme en question

Variables :
-liste_de_A EST DU TYPE LISTE
-liste_de_B EST DU TYPE LISTE
-liste_de_C EST DU TYPE LISTE
[ainsi jusqu'à la liste_de_L]
-D EST DU TYPE NOMBRE
-A EST DU TYPE NOMBRE
-i EST DU TYPE NOMBRE
-j EST DU TYPE NOMBRE
DEBUT ALGORITHME :
-LIRE D
-LIRE A
-liste_de_A[1]PREND LA VALEUR 10000:267.5:10000:10000:10000:10000:10000:10000:10000:10000:10000:10000
[ainsi pour les listes suivantes avec d'autres valeurs correspondant aux distances entre les points]
-i PREND LA VALEUR D
-j PREND LA VALEUR 0
-TANT_QUE (i!=A) FAIRE
   DEBUT TANT QUE
   SI D==1
   i PREND LA VALEUR ALGOBOX_POS_MINIMUM(liste_de_A,1,12)
   SI (i==A)ALORS
   DEBUT SI
   AFFICHER i
   AFFICHER "vous êtes arrivés !"
   FIN SI
    SINON
    DEBUT SINON
    AFFICHER i
    D PREND LA VALEUR i
    j PREND LA VALEUR 1
    FIN SINON
   FIN SI
   SINON
   DEBUT SINON
   D PREND LA VALEUR i
   FIN SINON
SI D==2 ALORS
   DEBUT SI
   i PREND LA VALUER ALGOBOX_POS_MINIMUM(liste_de_B,1,12)
   SI i==j ALORS
    liste_de_B[5] PREND LA VALEUR 10000
    i PREND LA VALEUR ALGOBOX_POS_MINIMUM(liste_de_B,1,12)
    FIN SI
    SINON
    DEBUT SINON
     AFFICHER i
     D PREND LA VALEUR i
     j PREND LA VALEUR 2
     FIN SINON
   FIN SI
   SINON
    DEBUT SINON
    D PREND LA VALEUR i
    FIN SINON
[ les mêmes boucles sont répétés pour d==3 jusqu'à d==12]


Le but de ce programme étant d'afficher le plus petit chemin d'un point à un autre. il y a ici 12 points.

Posté par
Glapion Moderateur
re : Algorithme de Dijsktra 06-03-13 à 14:20

Oui mais ça n'est pas celui qui tourne, (ça aurait été mieux de le copier/coller en mode éditeur de texte)
et il manque par exemple un FIN_TANT_QUE

j'ai eu beau le retaper avec de la syntaxe valide, il ne fonctionne pas. Et puis j'ai un peu de mal à comprendre ta logique dans ce programme. Je crains ne pas pouvoir t'aider.

VARIABLES
liste_de_A EST_DU_TYPE LISTE
liste_de_B EST_DU_TYPE LISTE
D EST_DU_TYPE NOMBRE
A EST_DU_TYPE NOMBRE
i EST_DU_TYPE NOMBRE
j EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE D
LIRE A
liste_de_A[1] PREND_LA_VALEUR 10000:267.5:10000:10000:10000:10000:10000:10000:10000:10000:10000:10000
liste_de_B[1] PREND_LA_VALEUR 10000:267.5:10000:10000:10000:10000:10000:10000:10000:10000:10000:10000
i PREND_LA_VALEUR D
j PREND_LA_VALEUR 0
TANT_QUE (i != A) FAIRE
DEBUT_TANT_QUE
SI (D == 1) ALORS
i PREND_LA_VALEUR ALGOBOX_POS_MINIMUM(liste_de_A,1,12)
SI (i == A) ALORS
DEBUT_SI
AFFICHER i
AFFICHER "vous êtes arrivés !"
FIN_SI
SINON
DEBUT_SINON
AFFICHER i
D PREND_LA_VALEUR i
j PREND_LA_VALEUR 1
FIN_SINON
FIN_SI
SINON
DEBUT_SINON
D PREND_LA_VALEUR i
FIN_SINON
SI (D == 2) ALORS
DEBUT_SI
i PREND_LA_VALEUR ALGOBOX_POS_MINIMUM(liste_de_B,1,12)
SI (i == j) ALORS
liste_de_B[5] PREND_LA_VALEUR 10000
i PREND_LA_VALEUR ALGOBOX_POS_MINIMUM(liste_de_B,1,12)
FIN_SI
SINON
DEBUT_SINON
AFFICHER i
D PREND_LA_VALEUR i
j PREND_LA_VALEUR 2
FIN_SINON
FIN_SI
SINON
DEBUT_SINON
D PREND_LA_VALEUR i
FIN_SINON
FIN_TANT_QUE
FIN_ALGORITHME

Posté par
Glapion Moderateur
re : Algorithme de Dijsktra 06-03-13 à 14:25

Bonjour, tu as lu ça : , tu aurais peut-être dû suivre la logique du pseudo code qu'il y a dans cette page wikipedia.

Posté par
Allison
re : Algorithme de Dijsktra 06-03-13 à 19:02

Bonsoir,
Je suis désolée pour le programme mais je ne sais pas le copier/coller en mode éditeur de texte.
Sinon, oui j'ai déjà lu cette page. J'ai compris la logique utilisé et j'essaie d'appliquer la même mais par contre j'ai beaucoup de mal à comprendre leur pseudo-code...je ne vois pas comment le réutiliser.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !