Dijkstra et Boost

Dijkstra et Boost - C++ - Programmation

Marsh Posté le 18-07-2008 à 20:53:04    

Bonjour à tous,
 
j'ai besoin d'appliquer l'algo de Dijkstra sur un graphe défini avec Boost. Le graphe est défini via des "bundled properties" et j'appelle Dijkstra comme suggeré dans la doc officielle sur les bundled properties, ie un truc du genre :
 

Code :
  1. struct monTypeVertex
  2. {
  3.    ...
  4. };
  5. struct monTypeEdge
  6. {
  7.    double longueur;
  8. };
  9. typedef boost::adjacency_list<
  10.    boost::listS, boost::vecS, boost::bidirectionalS,
  11.    monTypeVertex, monTypeEdge> monTypeGraphe;
  13.    ...
  15. vector<double> distances(num_vertices(monGraphe));
  17. dijkstra_shortest_paths(monGraphe, monVertexDepart,
  18.    weight_map(get(&monTypeEdge::longueur, monGraphe))
  19.    .distance_map(make_iterator_property_map(distances.begin(),
  20.    get(vertex_index, monGraphe))));


 
Seulement je n'ai pas trop saisi comment récupérer les plus courts chemins par la suite (il faut dire que la doc n'est pas d'une clarté/simplicité incroyable). J'imagine qu'il y a une map de prédecesseurs associées aux sommets du graphe, mais je ne sais pas comment la récupérer et l'utiliser.
 
Merci d'avance pour votre aide  :jap:

Reply

Marsh Posté le 18-07-2008 à 20:53:04   

Reply

Marsh Posté le 18-07-2008 à 21:27:37    

le prototype est :
 

Code :
  1. void dijkstra_shortest_paths
  2.   (const Graph& g,
  3.    typename graph_traits<Graph>::vertex_descriptor s,
  4.    PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
  5.    VertexIndexMap index_map,
  6.    CompareFunction compare, CombineFunction combine, DistInf inf, DistZero zero,
  7.    DijkstraVisitor vis, ColorMap color = default)


 
le 3e argument contient la map des prédécesseurs. As tu regardé :
http://www.boost.org/doc/libs/1_35 [...] xample.cpp ???

Reply

Marsh Posté le 19-07-2008 à 18:07:14    

Merci, effectivement en m'acharnant un peu sur l'exemple, j'ai fini par comprendre. Au final, je fais mon appel comme ça :
 

Code :
  1. vector<double> distances(num_vertices(visibility));
  2. vector<VisibilityVertexDescriptor> predecesseurs (num_vertices(visibility));
  4. dijkstra_shortest_paths(monGraphe, monVertexDepart,
  5.    predecessor_map(&predecesseurs[0])
  6.    .weight_map(get(&monTypeEdge::longueur, monGraphe))
  7.    .distance_map(&distances[0]));


 
Note à benêts : (dans mon cas au moins), il fallait paramétrer le graphe avec boost::undirectedS et pas boost::bidirectionalS.

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed