
Hello all, BGL supports a lot of graph algorithms, and lots of stuff get default filled in when using vecS as container type of vertices. However things become pretty ugly when not using this container. Below I used a listS for both edges and vertices. Maybe it can help other people (and maybe somebody can cross check me). Note that some constructs could be bundled, but for clearity I explicitly wrote all things out. I use the graph from the BGL book as example (figure 13.3). void TestgraphDijkstra() { typedef boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, std::string> Graph; typedef boost::graph_traits<Graph>::vertex_descriptor VertexDescriptor; typedef boost::graph_traits<Graph>::edge_descriptor EdgeDescriptor; typedef int Weight; typedef std::map<EdgeDescriptor, Weight> WeightMap; typedef std::map<VertexDescriptor, size_t> VertexIndexMap; typedef std::map<VertexDescriptor, Weight> DistanceMap; typedef std::map<VertexDescriptor, VertexDescriptor> PredecessorMap; Graph graph; WeightMap mapWeigth; VertexIndexMap mapVertexIndex; DistanceMap mapDistance; PredecessorMap mapPredecessor; boost::associative_property_map<WeightMap> pmWeigth(mapWeigth); boost::associative_property_map<VertexIndexMap> pmVertexIndex (mapVertexIndex); boost::associative_property_map<DistanceMap> pmDistance(mapDistance); boost::associative_property_map<PredecessorMap> pmPredecessor (mapPredecessor); //build a graph according to figure 13.3 //add vertices const VertexDescriptor vA = boost::add_vertex(graph); const VertexDescriptor vB = boost::add_vertex(graph); const VertexDescriptor vC = boost::add_vertex(graph); const VertexDescriptor vD = boost::add_vertex(graph); const VertexDescriptor vE = boost::add_vertex(graph); //set vertex names graph[vA] = "A"; graph[vB] = "B"; graph[vC] = "C"; graph[vD] = "D"; graph[vE] = "E"; //add edges const EdgeDescriptor eAC = boost::add_edge(vA, vC, graph).first; const EdgeDescriptor eBB = boost::add_edge(vB, vB, graph).first; const EdgeDescriptor eBD = boost::add_edge(vB, vD, graph).first; const EdgeDescriptor eBE = boost::add_edge(vB, vE, graph).first; const EdgeDescriptor eCB = boost::add_edge(vC, vB, graph).first; const EdgeDescriptor eCD = boost::add_edge(vC, vD, graph).first; const EdgeDescriptor eDE = boost::add_edge(vD, vE, graph).first; const EdgeDescriptor eEB = boost::add_edge(vE, vB, graph).first; const EdgeDescriptor eEA = boost::add_edge(vE, vA, graph).first; //set edge weights boost::put(pmWeigth, eAC, 1); boost::put(pmWeigth, eBB, 2); boost::put(pmWeigth, eBD, 1); boost::put(pmWeigth, eBE, 2); boost::put(pmWeigth, eCB, 7); boost::put(pmWeigth, eCD, 3); boost::put(pmWeigth, eDE, 1); boost::put(pmWeigth, eEB, 1); boost::put(pmWeigth, eEA, 1); //build index map boost::put(pmVertexIndex, vA, 0); boost::put(pmVertexIndex, vB, 1); boost::put(pmVertexIndex, vC, 2); boost::put(pmVertexIndex, vD, 3); boost::put(pmVertexIndex, vE, 4); //note: color map not needed, because of index map? boost::dijkstra_shortest_paths(graph, vA, boost::weight_map (pmWeigth).vertex_index_map(pmVertexIndex).distance_map (pmDistance).predecessor_map(pmPredecessor)); for (DistanceMap::const_iterator itDist = mapDistance.begin(); itDist != mapDistance.end(); ++itDist) { //dump const VertexDescriptor v = itDist->first; const VertexDescriptor vPrev = mapPredecessor[v]; std::cout << "Distance(" << graph[v] << ") = " << itDist->second << ", " << "Parent(" << graph[v] << ") = " << graph[vPrev] << std::endl; } }