title: BGL Dijkstra Shortest Paths with Bundled Properties
body: <p>I'm trying to use the dijkstra shortest path algorithm in BGL to compute a simple ST path on an unweighted undirected graph.  I may care about edge weights in the future, but for now I just want to consider edge traversals to be a uniform cost.</p>
  
  <p>I am also tracking multiple edge and vertex properties so I've based what I've done so far on the <a href="http://programmingexamples.net/wiki/CPP/Boost/BGL/BundledProperties" rel="nofollow">bundled properties example</a> that seemed to be the closest to what I'm attempting to do.</p>
  
  <p>Now I'm trying to figure out how to get dijkstra working so I can do my ST search but I am getting stuck on getting the right parameters set up for it.</p>
  
  <p>Here's a simplified example of the code I have so far:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  
  #include &lt;boost/config.hpp&gt;
  #include &lt;boost/graph/graph_traits.hpp&gt;
  #include &lt;boost/graph/adjacency_list.hpp&gt;
  #include &lt;boost/graph/dijkstra_shortest_paths.hpp&gt;
  #include &lt;boost/property_map/property_map.hpp&gt;
  
  // Create a struct to hold properties for each vertex
  typedef struct VertexProperties
  {
    int p1;
  } VertexProperties;
  
  // Create a struct to hold properties for each edge
  typedef struct EdgeProperties
  {
    int   p1;
  } EdgeProperties;
  
  // Define the type of the graph
  typedef boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties&gt; Graph;
  
  
  int main(int,char*[])
  {
    // Create a graph object
    Graph g;
  
    // Add vertices
    Graph::vertex_descriptor v0 = boost::add_vertex(g);
    Graph::vertex_descriptor v1 = boost::add_vertex(g);
    Graph::vertex_descriptor v2 = boost::add_vertex(g);
  
    // Set vertex properties
    g[v0].p1 = 1;
    g[v1].p1 = 2;
    g[v2].p1 = 3;
  
    // Add edges
    std::pair&lt;Graph::edge_descriptor, bool&gt; e01 = boost::add_edge(v0, v1, g);
    std::pair&lt;Graph::edge_descriptor, bool&gt; e02 = boost::add_edge(v1, v2, g);
  
    // Set edge properties
    g[e01.first].p1 = 1;
    g[e02.first].p1 = 2;
  
    std::cout &lt;&lt; "num_verts: " &lt;&lt; boost::num_vertices(g) &lt;&lt; std::endl;
    std::cout &lt;&lt; "num_edges: " &lt;&lt; boost::num_edges(g) &lt;&lt; std::endl;
  
    // compute ST shortest paths here...
  
    return 0;
  }
  </code></pre>
  
  <p>I'm getting tripped up on the right parameters for the call to dijkstra's algorithm.  They take the graph, a starting vertex, and then a predecessor map and distance map.  The examples I've seen so far, like <a href="http://programmingexamples.net/wiki/Boost/BGL/DijkstraComputePath" rel="nofollow">this one</a> set up their graph with just an edge weight without the bundled edge properties, which simplifies things.</p>
  
  <p>Ultimately, I'm after the ST shortest path so I'd need to recover the path from S to T.  From the looks of things, we need to set up a predecessor map and then we can use that to extract the path from a particular T back to S?</p>
  
  <p>I should also note that the environment I'm in does not allow C++11 language features. :(</p>
  
  <p>Any help here would be greatly appreciated!</p>