Algorithme du plus court chemin

**greg3105** · 29/04/2006, 16h36

Bonjour à toutes et à tous!!!

Je viens a vous car j'ai un petit soucis.

Je souhaiterais arriver a calculer un trajet de métro.

Je m'explique: j'ai un fichier texte qui comprends les ligne de métro avec les differentes stations.

Je voudrais permettre à l'utilisateur d'entrer ces deux stations (départ et arrivée) et ensuite que le programme calcul les routes pour le trajet avec les changement de lignes.

Mon problème en ce moment est que je n'arrive pas à imaginer l'algorithme me permettant de calculé la route de mon trajet.

Si quelqu'un pourrais m'éclairer ce serais très aimable.

Cordialement,

Greg3105

**afrikha** · 29/04/2006, 16h47

Où est le rapport avec java

le forum algorithme sera plus adéquat pour ton post...

**Scorpyosis** · 29/04/2006, 17h03

Ton probleme est un probleme connu ... d'algorithmique et non de java. Allez une petite aide tape "algorithme de dijkstra moore java" dans google il va te donner ce que tu cherches, et si tu me demandes pourquoi d...moore je t'envoie sur wikipedia

**mathk** · 29/04/2006, 17h08

ou alors ta toute la branche des algorithmes evolutives

**Razgriz** · 29/04/2006, 17h57

Pour parler un peu des plus courts chemins, il existe plusieurs types de situation :

1 . l'environnement est en 2D libre (ou dans le vide 3D), auquel cas le chemin le plus court est la ligne droite (pour les chemins, l'algotithme est connu).

2. l'environnement est en 2D ou en 3D mais on ne peut pas passer partout (comme dans le cas des métros, on traverse pas les murs, et pour un avion qui volle, il ne peut pas traverser la Terre)...
Dans le cas d'un avion par exemple, le chemin le plus court consiste à parcourir l'arc de cercle section entre la sphère, et le plan constitué de son centre, du point de départ et de destination.
Mais pour vous amuser, imaginer une fourmi sur un donut, quel est le chemin le plus court??? Pas facile lol...