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 :

Algorithme de Bellman-Ford


Sujet :

Algorithmes et structures de données

  1. #1
    Membre du Club
    Homme Profil pro
    Inscrit en
    Février 2014
    Messages
    80
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Février 2014
    Messages : 80
    Points : 46
    Points
    46
    Par défaut Algorithme de Bellman-Ford
    Bonsoir à tous,

    j'ai un peu du mal avec l'algorithme de bellman ford si quelqu'un peut m'aider s'il vous plait, merci.

    voici une photo de l'algorithme

    Nom : bellmanford.png
Affichages : 2283
Taille : 45,7 Ko



    donc au départ on initialise U avec le noeud source,ce que je ne comprends pas c'est que U n'est pas mit à jour dans l'algorithme?

  2. #2
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 609
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 609
    Points : 188 580
    Points
    188 580
    Par défaut


    Cet algo sert à calculer la distance d'un nœud donné à tous les autres, il ne fait pas uniquement le meilleur chemin entre deux points.

    Ensuite, ton u change à chaque itération (chaque valeur de i), puisque tu considères tous les arcs [l'un après l'autre, ils deviennent (u,v)]. Ton schéma n'indique pas que u est ta source (ce n'est que le premier nœud de l'arc considéré dans la boucle intérieure).
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  3. #3
    Membre du Club
    Homme Profil pro
    Inscrit en
    Février 2014
    Messages
    80
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Février 2014
    Messages : 80
    Points : 46
    Points
    46
    Par défaut
    merci pour ta réponse, en fait j'ai toujours du mal à comprendre


    par exemple : on veut aller du sommet A à F

    première itération je met à jour le poid du sommet B et C :

    A B C D E F
    0 2 4 infini infini infini



    2ème itération :

    c'est la que je comprends pas donc d'apres moi ca devrait
    être çà le résultat c-a-d qu'on exécute juste le sommet B


    A B C D E F
    0 2 4 5 5 infini





    alors que dans la vidéo que je regarde il execute le sommet B et C aussi et obtient cette matrice

    A B C D E F
    0 2 4 -1 5 infini

  4. #4
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 609
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 609
    Points : 188 580
    Points
    188 580
    Par défaut
    On ne passe pas que sur un seul sommet, mais bien sur tous : tant B que D servent à mettre à jour des valeurs. Si tu ne parcours pas tous les arcs (ou un sous-ensemble très bien choisi), alors l'algorithme n'est pas forcément correct (voir https://en.wikipedia.org/wiki/Bellma...of_correctness, par exemple) : avec ce que tu fais, à l'itération i=15, tu n'auras pas considéré tous les chemins d'au plus quinze nœuds depuis l'origine.
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  5. #5
    Membre du Club
    Homme Profil pro
    Inscrit en
    Février 2014
    Messages
    80
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Février 2014
    Messages : 80
    Points : 46
    Points
    46
    Par défaut
    dsl mais je ne comprends toujours pas , en faite la boucle principale c'est de 1 à nb sommet -1, donc il y aura 5 iteration, pourquoi dites-vous 15?

Discussions similaires

  1. Trouver l'arborescence des plus courts chemins (algorithme de Bellman-Ford)
    Par geforce dans le forum Algorithmes et structures de données
    Réponses: 12
    Dernier message: 11/03/2015, 06h39
  2. Trouver les chemins les plus courts avec l'algorithme de Bellman-Ford
    Par geforce dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 06/02/2015, 17h28
  3. Bellman-Ford algorithm problème
    Par ImmoTPA dans le forum C++
    Réponses: 29
    Dernier message: 03/08/2014, 19h18

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