C++

Dijkstra et Boost

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Dijkstra et Boost

fhr

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 :

struct monTypeVertex
{
...
};
struct monTypeEdge
{
double longueur;
};
typedef boost::adjacency_list<
boost::listS, boost::vecS, boost::bidirectionalS,
monTypeVertex, monTypeEdge> monTypeGraphe;
...
vector<double> distances(num_vertices(monGraphe));
dijkstra_shortest_paths(monGraphe, monVertexDepart,
weight_map(get(&monTypeEdge::longueur, monGraphe))
.distance_map(make_iterator_property_map(distances.begin(),
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:

Publicité

Joel F

Real men use unique_ptr

le prototype est :

Code :

void dijkstra_shortest_paths
(const Graph& g,
typename graph_traits<Graph>::vertex_descriptor s,
PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
VertexIndexMap index_map,
CompareFunction compare, CombineFunction combine, DistInf inf, DistZero zero,
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 ???

fhr

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

Code :

vector<double> distances(num_vertices(visibility));
vector<VisibilityVertexDescriptor> predecesseurs (num_vertices(visibility));
dijkstra_shortest_paths(monGraphe, monVertexDepart,
predecessor_map(&predecesseurs[0])
.weight_map(get(&monTypeEdge::longueur, monGraphe))
.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.

FORUM HardWare.fr

Programmation

C++

Dijkstra et Boost

Sujets relatifs
boost filesystem & fichiers en lecture seule	Compiler Boost sous MacOS X en STATIC
Utilisation boost::spirit	Un usage de boost::function dans un appel à boost::thread
Usage de Singleton de Boost::Detail::Thread ?	Pourquoi Boost n'implemente pas sa class STRING ?
VISUAL Intégrer une librairie directement dans un executable (boost+)	Probleme boost regex
BOOST::RANDOM pas random du tout :(	[C++] Tests Unitaires avec Boost
Plus de sujets relatifs à : Dijkstra et Boost

Page générée en 0.059 secondes