Bonjour. j’aimerai avoir l’exécution de l’algorithme de Bellman-ford avec ce graphe s’il vous plait
merci d’avance
Bonjour, ta demande n’est pas très claire. Tu dois exécuter Bellman-ford sur ce graphe ?
Peux-tu poster une image héberger sur ZdS ? Ou mieux retaper l’énoncé. Le PDF c’est bien mais il va disparaître (quand il sera supprimé de Drive) et ton message ne sera plus compréhensible.
Je ne comprends pas ta demande. L’exercice 2 porte sur l’algorithme de Dijkstra.
On prend le graphe de l’exercice 2 On l’execute avec Bellman Ford(donc pas la peine de regarder le pdf en entier mais seulement le graphe)
Quel problème cela te pose-t-il ?
Quel problème cela te pose-t-il ?
Au fait je veux savoir comment ça se fait. J’ai essayé Mais je n’y arrive pas
Tu peux appliquer le peudo-code suvant (xikipedia) :
fonction Bellman-Ford(G = (S, A), poids, s)
pour u dans S faire
| d[u] = +∞
| pred[u] = null d[s] = 1
//Boucle principale
pour k = 1 jusqu’à taille(S) - 1 faire
| pour chaque arc (u, v) du graphe faire
| | si d[v] > d[u] + poids(u, v) alors
| | | d[v] := d[u] + poids(u, v)
| | | pred[v]:= u
retourner d, pred
Tu peux aussi compléter un tableau du style :
a b c d e f g h
0 - - - - - - -
0 8 - 3 2 - - -
0 8 6 3 2 - - 5
….
a la fin, je trouve :
plus courte distance pour chaque sommet de d’arrivée:
a-0
b-7
c-6
d-3
e-2
f-5
g-6
h-5
Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte