Hello world
 
Je bute sur un truc avec l'utilisation de l'implé de Dijkstra par boost (voir l'exemple http://www.boost.org/doc/libs/1_51 [...] ample.cpp)
 
En gros, une fois que j'ai utilisé :
dijkstra_shortest_paths(g, s, &p[0], &d[0], weightmap, indexmap, std::less<int>(), closed_plus<int>(), (std::numeric_limits<int>::max)(), 0,default_dijkstra_visitor());
 
J'ai les distances du plus court chemin entre mon nœud d'origine et chaque nœud, ça, d'accord.
 
Moi ce que j'aimerai, c'est également avoir tous les nœuds par lequel on est passé lors de ce plus court chemin. Je suppose que ce doit être faisable, c'est quand même un usage de base, mais j'arrive pas à trouver des infos là dessus
 
Merci d'avance pour votre aide là dessus
 
En fait, l'idée c'est que certains nœuds de mon graphe sont spéciaux. J'ai besoin de connaitre les chemins vers les spéciaux voisins ; soit, s'il y a un spécial sur le chemin parcouru, on s'arrête là et on ne considère plus la suite du chemin. Pour cela, j'ai donc besoin de connaitre les noeuds parcourus par le chemin.
 
+
Aiseant

Tu peux essayer de ré-implementer Djikstra toi-même, l'algo en soit est assez simple, et tu auras toutes les informations requise. Et Djikstra parcourt tous les chemins me semble-t-il

la philosophie de boost.graph est de passer un visiteur a ton algo de parcours. Si tu veux le chemin parcouru, implemente un visitor qui accumule le snodes au fur et a mesure dna sun list.

Ben en fait c'est à ça que sert le p dans les params (pour predecessor map) et comme son nom l'indique permet de retrouver le chemin par lequel on est passé (par contre ce n'est pas valable dans le cas des graphes multiples, i.e. avec plusieurs arcs parallèles entre deux nœuds). Donc au final dans d[i] tu as la distance entre s et i et dans p[i] tu as le nœud prédécesseur de i dans le plus court chemin de s à i (et donc p[p[i]] le prédécesseur du prédécesseur etc..) dans p[s] y'a s ce qui donne la condition d’arrêt.