Discussion :

[wear12]

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





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?

[dourouc05]

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).

[wear12]

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

[dourouc05]

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.

[wear12]

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?