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

    Informations forums :
    Inscription : février 2014
    Messages : 69
    Points : 44
    Points
    44

    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 : 64
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


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherches
    Inscrit en
    août 2008
    Messages
    22 268
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

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

    Informations forums :
    Inscription : août 2008
    Messages : 22 268
    Points : 121 440
    Points
    121 440

    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 ou PyQt (tutoriels, FAQ, traductions) ? Contactez-moi par MP.

    Nouveau ! 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
    69
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : février 2014
    Messages : 69
    Points : 44
    Points
    44

    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


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherches
    Inscrit en
    août 2008
    Messages
    22 268
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

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

    Informations forums :
    Inscription : août 2008
    Messages : 22 268
    Points : 121 440
    Points
    121 440

    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 ou PyQt (tutoriels, FAQ, traductions) ? Contactez-moi par MP.

    Nouveau ! 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
    69
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : février 2014
    Messages : 69
    Points : 44
    Points
    44

    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 Général Algorithmique
    Réponses: 12
    Dernier message: 11/03/2015, 05h39
  2. Trouver les chemins les plus courts avec l'algorithme de Bellman-Ford
    Par geforce dans le forum Général Algorithmique
    Réponses: 3
    Dernier message: 06/02/2015, 16h28
  3. Bellman-Ford algorithm problème
    Par ImmoTPA dans le forum C++
    Réponses: 29
    Dernier message: 03/08/2014, 18h18

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