1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2018
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 20
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2018
    Messages : 1
    Points : 1
    Points
    1

    Par défaut Algorithme du plus court chemin

    Voila mon probleme, mon but est de creer un algorithme pour trouver le plus court chemin, le contexte est le suivant :
    Une fourmiliere est composé de plusieur salles , certaines sont reliées a d'autres par des tunnels , il y a une salle de depart et une de sortie , chaques salles sont reliées a une ou plusieurs autres salles, le but est de trouver le moyen de faire parvenir une fourmie de la salle de depart a la salle de sortie en faisant le moins de deplacement possible , sachant qu'ici , chaque salle est separé d'une distance de 1 , le deplacement est dont considéré comme instantané, c'est d'ailleur ce qui me pose probleme pour mon algo , car je ne peux pas utiliser Dijkstra.
    Merci pour ceux qui sauront m'aiguiller

  2. #2
    Modérateur
    Avatar de dinobogan
    Homme Profil pro
    ingénieur
    Inscrit en
    juin 2007
    Messages
    4 034
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France

    Informations professionnelles :
    Activité : ingénieur
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : juin 2007
    Messages : 4 034
    Points : 7 187
    Points
    7 187

    Par défaut

    il n'y a aucune raison pour que tu ne puisses pas utiliser l'algorithme de Dijkstra. Le cout de chaque arc est de 1.
    Qu'est-ce qui te bloque ?
    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java
    Que la force de la puissance soit avec le courage de ta sagesse.

  3. #3
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 910
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 910
    Points : 6 835
    Points
    6 835

    Par défaut

    Bonjour

    Je vais volontairement répondre à côté de la question. (Pour ouvrir des horizons)

    Si tu cherches le plus court chemin pour une fourmi, alors Dijkstra est là.
    Mais s'il y a toute une fourmilière derrière, la question n'est pas tellement celle de plus court chemin, mais celle du flot maximal.
    Et là, le conseil est d'utiliser l'algorithme de Ford-Fulkerson pour calculer un flot maximal.

    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  4. #4
    Membre averti
    Inscrit en
    janvier 2005
    Messages
    507
    Détails du profil
    Informations forums :
    Inscription : janvier 2005
    Messages : 507
    Points : 441
    Points
    441

    Par défaut

    Salut. Je vous conseil l'algorithme de ford
    Deux, n'apprendront pas; le timide et l'arrogant

  5. #5
    Membre confirmé
    Profil pro
    Directeur Scientifique
    Inscrit en
    avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 45
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : avril 2005
    Messages : 419
    Points : 570
    Points
    570

    Par défaut

    Pour le plus court chemin en nombre d'arcs, un parcours en largeur d'abord suffit.

Discussions similaires

  1. Recherche algorithme de plus court chemin
    Par WileECoyote dans le forum Intelligence artificielle
    Réponses: 1
    Dernier message: 20/02/2011, 15h44
  2. Algorithme du plus court chemin
    Par ndjeur dans le forum Débuter
    Réponses: 2
    Dernier message: 29/12/2009, 15h00
  3. Algorithme du plus court chemin
    Par Didier77 dans le forum C
    Réponses: 4
    Dernier message: 24/05/2007, 20h54
  4. Algorithme du plus court chemin
    Par greg3105 dans le forum Algorithmes et structures de données
    Réponses: 13
    Dernier message: 04/05/2006, 17h26
  5. Algorithme du plus court chemin
    Par greg3105 dans le forum Langage
    Réponses: 6
    Dernier message: 29/04/2006, 20h02

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