Version imprimable
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
Pièce jointe 306904
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?
:salut:
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).
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
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.
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?
