Discussion :

[chakirlbr]

Bonjour a tous ,

je voudrai créer un programme qui affichera les différents lignes à prendre et les stations où doit se faire le changement. pour aller de la station A a une Station B .

j'ai créer 2 classes station et ligne ;

ligne1,2,3 et 4 sont des tableau de station

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Station ligne1[]={A,A1,A2,A3,A4,AA};
Station Ligne2[]={X,X1,A1,X2,X3,X4,X5,Y};
Station Ligne3[]={B,B1,B2,B3,X2,A2,B4,B5,B6};
Station Ligne4[]={G,X1,H,B5,I,J,K,X4,B1,M};

l'utilisateur va saisir la station de départ et celle d’arrivée.

les points d'intersection sont des Station ou il peut faire un changement d'une ligne a une autre .

merci d'avance pour votre aide .

[toufik135]

Utilise l'algorithme de Dijkstra

Sinon je sais pas, tu pourrais pour chaque élément de chaque tableau déterminer au moment ou il est le point de départ lequel est son point d'intersection... et tu stock toutes ces données
dans un tableau à 2 dimension ou Map<String,String> ... ou Integer ça dépend comment tu le vois.

[hwoarang]

C'est un classique probleme de recherche du meilleur chemin dans un graphe. Ca peut se résoudre, comme l'a fait remarquer toufik135, avec l'algorithme de Dijkstra ou, si tu as les coordonnées GPS, la variante (plus efficace qui favorise le chemin le plus court) : l'algorithme A star.

il faut savoir que plus le nombre de gare augmente, plus l'algorithme sera lent (exponentiellement). Il faudrait donc que tu essaies d'avoir une idée du nombre de lignes/stations que tu veux gérer au maximum. De la, tu pourras décider si tu as besoin d'utiliser des optimisations ou non. Par exemple, pré-calculer des meilleurs chemins.

[chakirlbr]

je veux pas m’afficher juste le chemin plus court , il doit m’affiche tous les chemin possible a la station de destination.

[zaza576]

Hello,

dans ce cas, nous te redirigeons (comme pour l'algorithme de Djikstra) vers la théorie des graphes.

Cherche un peu comment implémenter le "parcours de graphe en profondeur". Cela te donneras naturellement un algorithme pour implémenter ta solution.

Reviens nous voir avec un peu de code.

[Jarek_Mace]

Salut !

J'ai réalisé, il y a peu, un algorithme où je devais de même présenter tous les chemins possibles d'une liste comprenant n villes.

Et pour m'aider, j'ai d'abord réalisé une fonction permutation, qui m'affiche les n! permutations possibles d'une liste.
C'est une fonction récursive.

Par contre, j'ai l'impression que vu ta description, tu as l'air d'avoir pas mal de "stations" à visiter, alors tu auras, je pense, beaucoup d'affichage !

Pour 10 villes à visiter, j'ai attendu plus de 7000 secondes (2 heures)...

Par contre, j'ai peur qu'avec un parcours en profondeur, tu fasses bien un chemin complet où tu visiteras toutes tes stations, mais je ne pense pas que cela te donne toutes les possibilités.