demande d'un algorithme pour trouver un plus court chemin

Ben cet algo est justement fait pour ça ! ;-)
Il suffit de représenter ton problème sous forme de graphe et d'appliquer l'algo.

Merci CRicky

D'après ce que j'ai compris il faut faire un tableau à deux dimensions de taille nombre_de_positions * nombre_de_positions et ça me paraît énorme. En plus je ne vois pas de récursion là-dedans et je pense que si on pouvait en caser une quelque part ça optimiserait un peu l'algo, non?

J'ai aussi entendu parler de l'algorithme A* mais apparemment il ne garantit pas de trouver le plus court chemin.

Qu'est-ce que tu en penses?

esk

Tu peux faire un tableau mais ce n'est pas ce que je ferai pour la limite de mémoire rapidement atteinte.
Moi j'aurais mis une classe ou structure représentant une case, et un pointeur ou référence sur toutes les cases accessibles.
Ce pointeur ou référence étant accompagné d'une valeur indiquant le longueur de parcourt entre les 2 cases.

Ensuite si tu n'as pas de récursivité tant mieux puisqu'il faut généralement l'éviter.

Bonjour CRicky,

En fait c'est un projet que j'ai à faire. J'ai une matrice de taille 26*26 et je dois trouver (comme tu l'as déjà compris j'imagine) le plus court chemin entre deux positions (déterminées) dans la matrice.
Au départ je pensais représenter les positions de la matrice par un tableau et le parcourir en largeur mais ça m'a l'air drôlement compliqué.
Pour Dijkstra, le problème est que je n'ai jamais étudié les graphes et je ne comprends pas bien les algorithmes que j'ai lu sur le net.
Quand on est à une position donnée (par exemple au départ), comment est-ce que je choisis vers quelle direction aller en premier sachant qu'une arrête entre 2 positions a toujours une valeur de 1. Ou alors, à chaque position, comment traiter tous les successeurs en même temps?
Je me demande aussi s'il ne faut pas ajouter, à chaque position, un pointeur vers le prédecesseur pour gérer les retour en arrière.
Ça fait beaucoup de questions je sais mais en faite je suis assez perdue avec cet algorithme.

Merci de m'aider.

esk

Bon et bien l'algorithme de dijkstra c'est pour résumer prendre toutes les directions possibles (y compris les retours sur soi-même) suivant une règle.
Sur chaque case tu mets la distance parcourue depuis le début.

La règle est que si lorsque tu arrive sur une case qui a déjà été parcourue, tu as 2 cas:
- soit avant le passage courant la distance est plus courte, alors tu écrases l'ancienne valeur par la nouvelle
- soit la distance était plus courte, alors tu n'écrase pas et tu considère que c'est une impasse (un autre passage pour arriver à cette case est plus court, on garde celui-là).
Cette règle va donc empêcher de faire demitour car la valeur sera > 2 à celle qui était déjà.

Voilà, il faut ajouter de la récursivité car tu a au maximum 4 passages possible pour une case normale donc 4 nouveaux passages possibles pour chaque nouvelles cases (la règle diminue en fait le nombre de cases restante).
Et la récursivité s'arrête lorsque touts les chemins ont été faits pouisqu'on ne pourra plus avancer nullepart (bloqué par des cases de distances plus courtes ou égales).

C'est justement cette récursivité que je n'arrive pas à faire.

Est-ce que tu pourrais m'écrire vite fait un algo de la fonction récursive? Je ne sais pas comment le "marérialiser".

Merci

esk

Je pense que tu ne devrait pas chercher à faire de la récursivité mais chercher à appliquer l'algo (là tu te rendras compte qu'il faut de la récursivité).
tu auras une fonction du genre TraiteCase(ligne, colonne, distance_parcourue) dans laquelle tu fais tes tests et calculs.
A la fin de ta fonction, il fuat se dire que tu dois traiter les cases autours:
TraiteCase(ligne - 1, colonne, nouvelle_distance_parcourue)
TraiteCase(ligne + 1, colonne, nouvelle_distance_parcourue)
TraiteCase(ligne, colonne - 1, nouvelle_distance_parcourue)
TraiteCase(ligne, colonne + 1, nouvelle_distance_parcourue)

Bonjour, je dois faire le même projet, et naturellement je galère beaucoup pour faire l'algo.
Es tu arrivé à le faire?

Par "faire" un alogorithme, tu entends créer l'algorithme en partant de rien? Où implémenter un algorithme dans un langage particulier?



C'est un algorithme que nous a donné notre prof de maths pour que nous l'implémentions en C... Si ca t'interesse je dois avoir le code source quelque part sur mon PC (fonctionne sous linux avec une surcouche graphique pour les xlibs)...

Je dois faire le programme sous Scilab.
Et même ton truc je ne comprends pas trop comment il fonctionne.
En faite j'aimerai au départ comprendre réellement l'algo de dijkstra et essayer de l'implémenter sous Scilab

Ah, désolé, mais je ne connais pas Scilab... Je peux pas t'aider la dessus... Ensuite, étant donné que je suis une daube en ce qui concerne les algorithmes, j'aurais bien du mal à t'expliquer comment cela marche (je suis même pas sur d'avoir compris  )

En gros, pour simplifier, tu dessines ton graphe avec le point de départ et le point d'arrivée.
Le but est d'écrire sur chaque sommet la distance parcourue du point de départ à cette case.
Pour optimiser le tout, il faut bien choisir quel sera le prochain sommet à calculer. Pour ça, il faut choisir le sommet qui a la plus petite distance et qui a encore des sommets autour.
En fait, cet algo permet d'avancer par niveaux sur la distance (1 puis 2 puis 3 etc).

Je n'utilise pas un graphe mais une matrice et je dois trouver le chemin le plus court en partant de gauche à droite.

Une matrice peut être vu comme un graphe où les sommets sont les cases de la matrice et où les arcs sont les différences des 2 valeurs de 2 cases jointes ;-)