Bonjour,

Voici l?énoncé du problème que l'on me pose :

Sire Gwendal, paludier à Guérande, en Pays de Loire, désire aller vendre sa récolte de sel dans l?une des 4 grandes foires de sa région : soit à Rennes (ville 11), soit à Louéac(ville12), soit à Pontivy (ville13), soit à Lorient (ville14).
Il connaît les gains qu?il peut faire dans chacune de ces 4 villes, à savoir respectivement 550, 580 , 590 et 600 écus. Il connaît aussi les différents itinéraires pouvant le mener de Guérande (ville0)à chacune des 4 villes, mais à chaque village, ville ou pont, il doit s?acquitter d?un droit de passage.

villes	1	2	3	4	5	6	7	8	9	10	11	12	13	14
octrois en ecus	10	12	15	5	15	10	3	10	5	20	4	5	20	7

Suggestion : Associons aux différents arcs (x,y) une valeur v(x,y) égale à l'opposé de l'octroi dont on doit s'acquitter au passage de la ville y (ainsi la valuation de l'arc (2,4) est égale a -5) et complétons le graphe en lui ajoutant une sortie fictive, notée 15, et des arcs reliant les différentes foires, extrémités initiales de ces arcs. la valeur de chaque chemin allant de l'entrée (sommet 0) à la sortie (sommet 15) est égale à la somme des valuations des arcs le constituant, et représente le bénéfice réalise par le paludier si celui-ci emprunte le chemin correspondant. Associons à chaque sommet x une quantité g(x) représentant la valeur du chemin optimal allant de ce sommet à la sortie (évidement nous avons g(x)=0). Écrire le principe d'optimalité de Bellman dans le cas de ce paludier, et l'appliquer pour trouver le chemin optimal

Voila mon avancement pour l'instant :

le graphe : https://********
Bellman-Ford : http://*******

***image rapatriée***

Sauf que je ne trouve pas le principe d'optimalité de bellman ford ? J'ai bien son algorithme mais il ne semble pas que ce soit cela ?

Merci pour votre aide