Fonction de calcul du coût d'un chemin dans un graphe

bonsoir,
je veux traduire cette formule en algorithmique, mais je trouve des difficultés.
ayant une chaîne 'parcours', qui contient l'ensemble des sommets traversé dans un graphe, je doit déterminé le coût de ce parcours.

coût= Σij ( CF ij Y ij + CV ij X ij )

cette formule calcul le coût d'un graphe, i représente l'indice du sommet source, et j représente indice du sommet destinataire.
entre les sommets, chaque arc ij a un coût fixe CF et d'autre propriété CF, X, Y connue à l'avance (données).

le moindre indice ou conseil peu énormément m'aimer, merci.

:salut:

Ta question se décompose en deux parties, supposant que ton graphe soit déjà implémenté (par exemple, http://tcuvelier.developpez.com/tuto...onnees/#LVII-B) : représenter un parcours dans ton graphe (liste de points parcourus ou d'arêtes), représenter le coût d'une arête (la partie CF ij Y ij + CV ij X ij, associer les données aux arêtes : par exemple, un tableau indexé avec l'identifiant de l'arête et contenant ces données ou champs supplémentaires dans ta structure d'arête). Une fois que tu as posé ces bases, le reste devrait suivre ;).

Stocke des aspirines :D
Ta fonction objectif contient des coûts fixes, ce qui fait de ce cas une version encore plus compliquée que le Traveling Salesman Problem.

Blague à part, il faudrait une heuristique nouvelle, utiliser les nouvelles méthodes dites de point intérieur.
Personnellement, je te conseille un algo glouton (simple, compréhensible, avec une bon ratio développement/résultats).

Par exemple. :
- mapper les points sur un plan (comment faire ?)
- déterminer le barycentre des points
- minimiser la somme des carrés des médianes des noeuds.

J espère que d autres auront d autres idées pour t aider.