Discussion :

[ram-0000]

Bonjour,

J'ai une liste d'objet (dans un std::vector)
J'ai une liste de liens entre ces objets (en fait chaque objet de la liste précédente possède une liste de liens vers les objets suivants)

Je cherche maintenant un algorithme qui me permette de parcourir ce graphe plus ou moins bien connecté (c'est bien comme cela que cela s'appelle ?) depuis un objet A vers un objet B (et bien sûr par le plus cours chemin possible).

Je pense avoir vu ce type de problème sous le terme générique du "voyageur de commerce"

Ma question maintenant, existe t'il dans boost, un algo qui pourrait m'aider à régler mon problème ?

Merci de vos idées

[JolyLoic]

Tu as ce genre de chose dans boost::graph (cherche shortest path algorithm). Je crois que le problème du voyageur de commerce est tout autre : Son but est de passer par tous les points avec un coût minimal.

[ram-0000]

Tu as ce genre de chose dans boost::graph (cherche shortest path algorithm).

Je vais regarder de ce côté

Je crois que le problème du voyageur de commerce est tout autre : Son but est de passer par tous les points avec un coût minimal.

Tu as raison et j'avais tord, j'ai modifié le titre du post en conséquence, merci

[Matthieu Brucher]

Il me semble qu'il y a un Dijkstra dans Boost.Graph.

[loufoque]

Il y a aussi breadth-first search, A*, etc.