IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Chemin le pluscourt entre deux villes


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre à l'essai
    Inscrit en
    Mai 2008
    Messages
    5
    Détails du profil
    Informations forums :
    Inscription : Mai 2008
    Messages : 5
    Par défaut Chemin le pluscourt entre deux villes
    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

  2. #2
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 77
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Par défaut
    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.
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  3. #3
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  4. #4
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Par défaut
    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.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  5. #5
    Membre très actif
    Avatar de TheDrev
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    310
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Rhône (Rhône Alpes)

    Informations forums :
    Inscription : Novembre 2006
    Messages : 310
    Par défaut
    Regarde aussi l'algo de ford-bellman qui est assez simple d'accès

Discussions similaires

  1. [MySQL] Distance entre deux villes.
    Par HaDeSs dans le forum PHP & Base de données
    Réponses: 1
    Dernier message: 25/07/2012, 19h51
  2. Trouver distance/ itinéraire entre deux villes
    Par melles dans le forum Web & réseau
    Réponses: 6
    Dernier message: 09/03/2009, 18h22
  3. Distance entre deux villes
    Par mister3957 dans le forum Services
    Réponses: 3
    Dernier message: 13/09/2007, 10h05
  4. distance entre deux ville à partir de longitude/latitude
    Par sami_c dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 09/02/2007, 20h57
  5. calcul distance entre deux villes
    Par alexfrei04 dans le forum Access
    Réponses: 2
    Dernier message: 08/01/2007, 21h49

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo