recherche du chemin le plus court entre 2 points

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

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.

Citation:

---

Envoyé par JolyLoic

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

---

Je vais regarder de ce côté

Citation:

---

Envoyé par JolyLoic

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

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

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