demande d'un algorithme pour trouver un plus court chemin

Bonjour tout le monde,

Est-ce que quelqu'un pourrait me dire quel algorithme je pourrais utiliser pour trouver un plus court chemin.
On m'a dit que je pouvais utiliser Dijkstra de manière récursive mais je ne vois pas comment.
Si vous avez de meilleures idées ou si vous pouvez tout simplement m'éclairer sur celle-là ça m'aiderait vraiment beaucoup.

Merci merci.

esk

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

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

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

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

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

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).

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 ;-)