Bonjour,
J'ai un petit problème qui je pense est soluble à l'aide de la théorie des graphes. Je vais probablement utiliser un language approximatif, je n'ai pas étudié cette théorie et j'en ai juste la plus fine couche du vernis d'intuition.
Supposons que j'ai 3 sommets A_1 A_2 et V tels que:
A_1 et A_2 sont reliés par une arrête à laquelle j'associe la valeur a
(mais elle ne représente pas le coût pour passer de A_1 à A_2).
A_1 et V sont reliés par une arrête auquelle j'associe la valeur b
(mais, à nouveau, elle ne représente pas le coût pour passer de A_1 à V).
Je souhaiterai engendrer l'arrête A_2,V à laquelle j'associe la valeur a*b
J'ai simplifier au max mon problème mais dans le cas général, j'aurai
M sommets reliés entre eux ( combination( 2 M) arrêtes auxquelles j'ai associée une valeur -qui n'est pas pas un coût de passage- a_i_j).
Si par exemple, J'ai un autre sommet V relié à A_1 de "poids" r, il faut que j'engenre (M-1) autres arrêtes
V, A_i de "poids" r* a_1_i
En fait, ça revient à remplir une matrice symétrique.
ça paraît facile sur le papier mais à implémenter??
Est-ce facile à faire avec graph boost library?
Merci pour votre aide
Partager