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

 

  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 052
    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 052
    Points : 7 112
    Points
    7 112

    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
    3 170
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 170
    Points : 7 413
    Points
    7 413

    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
    511
    Détails du profil
    Informations forums :
    Inscription : janvier 2005
    Messages : 511
    Points : 445
    Points
    445

    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.

  6. #6
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    octobre 2017
    Messages
    19
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Israël

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : octobre 2017
    Messages : 19
    Points : 11
    Points
    11

    Par défaut

    Donc ton probleme est non pas le plus court chemin en terme de "distance" mais en nombre d'étapes ?

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