Théorie des graphes : Bellman-Ford appliqué aux poids minimums
Bonjour à tous,
Je suis confronté à un problème de théorie des graphes appliqué à l'algorithme de Bellman-Ford, dont voici l'intitulé (ex4 pj) :
- Supposons que le poids d'un chemin est calculé comme le produit du poids des arcs composant ce chemin, et non plus comme leur somme, comme cela était le cas pour les algorithmes de calcul des plus courts chemins. Au lieu de chercher un plus court chemin on cherche un chemin de poids minimum.
Nous avons besoin de la proposition suivante : L'algorithme de Bellman appliqué aux produits au lieu des sommes donne le chemin de poids minimum.
En fait, il manque une condition dans cette proposition. Ajouter la condition et démontrer la proposition.
_____
J'ai planché dessus toute une journée et ça a été totalement infructueux. Je suis d'abord parti du principe que le sommet de base était de poids 1 et non 0 comme ça l'était pour une somme (sinon, le poids minimum des chemins serait toujours nul).
Par contre, pour la condition à ajouter, j'ai fais chou blanc.
Instinctivement, je m'étais dis que cette condition pouvait peut-être être le nombre de poids des arcs négatifs dans le graphe. J'ai fais tourner l'algo sur plusieurs graphes, et c'est toujours bon... Donc j'en déduis que ça ne vient pas de ça.
J'ai essayé de faire tourner l'algorithme, un peu au pif je dois l'avouer, avec poids négatifs ou non, sur des structures de graphes un peu particulières (sommets sans arcs entrants ni sortants, avec 1/plusieurs entrants etc.), mais rien n'y fait, je bloque totalement.
Un connaisseur en la matière pourrait-il me donner une piste pour m'en sortir ?
Je vous remercie par avance,
Lucas
-----