Discussion :

[hervemoha]

j aimerai que vous puissiez m'aider pour l'implémentation d'un algorithme du plus court chemin en java. Chaque ville a ses coordonnées x et y , chaque ville est reliée par ses voisines et les distances entre villes sont connues.
J ai besoin de cet algo implémenté en java si possible
Merci de votre

[Zavonen]

Pour une implémentation en Java ou autre chose, il faut d'abord savoir comment sont représentées tes données.
J'opterais pour un tableau à double entrée avec les villes en abscisses et en ordonnées, comme dans les guides touristiques, sauf que ce tableau est incomplet ne figurent les distances A,B que quand A et B sont voisines. A partir de là il faut remplir tout le tableau.
C'est bien ça ?
Si oui. Un algo récursif se concoit ainsi:
Je cherche la distance de A à B.
A et B sont-elles voisines ?
Si oui chercher dans le tableau la distance de A à B et c'est fini.
Sinon, établir (par exemple au moyen du tableau) la liste des villes voisines de A
Calculer par appel récursif la distance à B de chacune de ses voisines et prendre le minimum de ces distances.

[pseudocode]

--> http://www.google.com/codesearch?q=dijkstra+lang%3Ajava

[ToTo13]

Bonjour,

en général on construit un graphe pour représenter les chemins possibles entre les villes.
A ce moment là, l'algorithme du plus court chemin entre deux villes est l'algorithme de Dijkstra. Tu en trouveras le pseudo code un peu partout sur le net ainsi que de très nombreuses implémentations.
Commence par faire une recherche sur le forum, sujet traité de multiple fois.

[TheDrev]

Regarde aussi l'algo de ford-bellman qui est assez simple d'accès