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

Langage C++ Discussion :

Implementer algo de Dijkstra


Sujet :

Langage C++

  1. #1
    Membre à l'essai
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 5
    Par défaut Implementer algo de Dijkstra
    bonjour a tous et bonnes fetes de fin d'année,
    j'ai un soucis avec l'algo de Dijkstra, je n'y arrive pas...
    j'ai actuellement une classe Graphe (non orienté), Sommet et Aretes et je me dois de trouver le plus court chemin d"un point a un autre avec dijkstra. le graphe est en fait un maillage régulier en forme de rectangle, un peu comme un quadrillage.
    pour l'instant je n'ai que initialiser : tous les sommets marqués à -1 (cad l'infini) et le sommet source à 0.
    mais ensuite...
    si vous pouviez m'aider, merci

    ps : j'ai dja regardé sur le net (wiki,etc...)

  2. #2
    Membre chevronné Avatar de Lavock
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    560
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 560
    Par défaut
    De mémoire, l'algo de dijkstra (imprononçable se nom ><) est super bourin -> il faut que tu parcours "tout" le graphe oO.

    Qu'est-ce qui te bloque réellement dans cette algorithme ? En gros, le but c'est de faire un arbre de parcours. Après, je suis pas sûr, mais je crois qu'il vaut mieux le parcourir de manière horizontale si tu fais du Dijkstra pure.

    Les optimisations principale sont => passage du parcours horizontale au parcours vertical "intelligent" ou semi-prévisioniste.

    Passage d'un arbre en graphe -> évité de calculer des portion de parcours déjà vu dans d'autre parcours.

    Mais surtout, au vue de la lourdeur de Dijkstra, es-tu sûr que c'est ce qu'il te faut ? Quelle sont tes domaine d'application ? Routage, jeu ?

  3. #3
    Membre à l'essai
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 5
    Par défaut
    mon application c'est : appliquer dijkstra a ce graphe
    mon probleme c'est que je n'arrive pas a l'implémenter...comment stocker les infos petit a petit

  4. #4
    Membre averti
    Profil pro
    Inscrit en
    Août 2008
    Messages
    15
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2008
    Messages : 15

  5. #5
    Expert éminent
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 635
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 635
    Par défaut
    Salut,
    Citation Envoyé par Lavock Voir le message
    De mémoire, l'algo de dijkstra (imprononçable se nom ><)
    on dirait quelqu'un qui éternue
    est super bourin -> il faut que tu parcours "tout" le graphe oO.
    Non, pas forcément...

    D'autant moins si les différentes arrêtes ne sont pas de taille égale (ce qui n'est, malheureusement, apparemment pas le cas du problème cité)
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  6. #6
    Membre à l'essai
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 5
    Par défaut
    oui j'ai vu, mais ca me parait un peu compliqué
    ne peut on pas créer une simple fonction dijkstra prenant en argumant le poitn de départ et d'arrivée, et en ne travaillant qu'avec des listes ?
    un peu comme ici : http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra ?

  7. #7
    Membre chevronné Avatar de Lavock
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    560
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 560
    Par défaut
    Citation Envoyé par koala01 Voir le message
    Non, pas forcément...

    D'autant moins si les différentes arrêtes ne sont pas de taille égale (ce qui n'est, malheureusement, apparemment pas le cas du problème cité)
    D'ou le tout entre guillemet => cela relève du pire des cas/ de ce qu'il faut chercher à faire.

    [EDIT pour répondre un peu quand même] Comme je l'ai dit, l'idée et de stocker les parcours dans un arbre. A chaque noeud de l'arbre correspond les éventualité de chemin différent.

    Chaque noeud à une valeur associé => le "temps" pour y arriver depuis le précédent noeud. Une nouvelle possibilité intervient ? Tu stockes la valeur temps dans ton noeud, tu reprend à 0 jusq'au prochain noeud. <= Cette description est un parcours en "profondeur" de l'arbre de parcours.

  8. #8
    Membre confirmé
    Homme Profil pro
    Développeur
    Inscrit en
    Décembre 2008
    Messages
    101
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Isère (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : Décembre 2008
    Messages : 101
    Par défaut
    Citation Envoyé par colamaya Voir le message
    oui j'ai vu, mais ca me parait un peu compliqué
    ne peut on pas créer une simple fonction dijkstra prenant en argumant le poitn de départ et d'arrivée, et en ne travaillant qu'avec des listes ?
    un peu comme ici : http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra ?
    Personnellement je l'ai implémenté en Java il y a peu et j'ai créé une classe qui prends dans le constructeur le graphe, puis une fonction qui me retournait toutes les distances (mon but était de trouver tout les noeuds qui était à une certaines distances). Avec les fonction initialisation et next en fonction privée de la classe.

    Pour ce qui est de l'algorithme, l'article de Wikipedia est peut être pas hyper claire parce qu'il découpe l'algorithme, mais ce n'est pas si compliqué.

    Je te conseille de d'abord essayer de simplement calculer la distance minimale de chaque noeud de ton graphe. C'est ce que fait l'algorithme de dijkstrat.

    Une fois que tu arrive à faire ça. Il faudra adapter l'algorithme pour se souvenir du chemin.

    La dernière étape seras d'optimiser l'ensemble parce que tu peut facilement te retrouver à consommer beaucoup de mémoire. Mais les structures de données vraiment optimisées pour Dijkstrat je te conseil de voir ça après coup.

Discussions similaires

  1. Implementation dijkstra en C
    Par BatuBou dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 01/01/2008, 22h48
  2. algo de dijkstra
    Par csimplecommetout dans le forum C
    Réponses: 4
    Dernier message: 14/02/2007, 15h03
  3. Besoin d'aide pour implementer un algo
    Par mobscene dans le forum Langage
    Réponses: 7
    Dernier message: 30/11/2006, 16h17
  4. programme algo de + court chemin (dijkstra)
    Par isidore dans le forum C
    Réponses: 7
    Dernier message: 28/11/2006, 12h38
  5. algo de Dijkstra (+ court chemin d'un labyrinthe)
    Par gg14bis dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 25/03/2005, 08h57

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