Recherche algorithme

[Cliffe]

Bonjour,

Je cherche un algo rapide pour trouver un chemin dans un graphe de poids maximal. Voici à quoi ressemble mes graphes :

[CENTER] [/CENTER]

L'idée est de partir du point vers le point sachant qu'on ne peut passer que par arcs (sur mon exemple ). Tous les arcs ou je n'est rien noté ont un poids nul.


Le graphe, pour faire simple : chaque sommet de gauche est relier à un sommet à droite et à un poids. Un sommet de droite est relié (ou non) à tous les sommets d'un groupe situer en dessous.


Merci.

[nodjim]

Si les poids sont tous positifs, tu peux déja au moins éliminer toutes les liaisons de p1,p2 ou p3 vers b. Et donc aussi les liaisons entre a et p4.

[Cliffe]

Si les poids sont tous positifs, tu peux déja au moins éliminer toutes les liaisons de p1,p2 ou p3 vers b. Et donc aussi les liaisons entre a et p4.

Aucun arcs ne peut être supprimer. Je comprend pas oO

[nodjim]

Je voulais juste dire que si tous les poids sont positifs, tu optimises en évitant les raccourcis. J'ai vaguement l'impression que la somme de tous les poids a une valeur fixe, je me trompe ?

[Dlzlogic]

Bonjour,
A mon avis l'algorithme de Dijkstra devrait vous satisfaire.