Demande d'un algorithme de plus court chemin

Merci crabs

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. Et je pense que si on pouvait caser une récursivité 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?

liza

Bonjour,

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?
Ça fait beaucoup de questions je sais mais en faite je suis assez perdue avec cet algorithme.

Merci de m'aider.

liza

C'est pas nécessairement un cas typique et il n'y a pas 1 plus court chemin (sauf cas particuliers) mais plusieurs...

Tu as le droit aux diagonales ou pas?

Dans le cas ou ta réponse est non:

Calcul Dx et Dy, si un des deux est nul=> la solution est immédiate plus besoin de faire des calculs savant

Sinon tu avances te déplaces d'abord sur un axe et ensuite sur l'autre, pas besoin de chercher un optimum, tant que tu te déplaces dans le bon sens sans aller trop loin tu seras sur un des plus courts chemins...

Si tu as le droit aux diagonales, c'est plus compliqué (sauf dans le cas ou les deux sont sur une même ligne (Dy=0) ou une même colonne (Dx=0) où là la solution est encore une fois immédiate...

Mais dans l'absolu il faut que tu te déplaces dans la diagonale vers ton point d'arrivée autant de fois que le plus petit de tes deux D puis après sur l'autre axe du nombre de fois restant, pas bien compliqué tout ça, rien à voir avec un parcours d'arbre :)
Always forgive your enemies
Nothing annoys them so much.

(Oscar Wilde)

(Oscar Wilde)