title: How to find the shortest path between two vertives in a graph?
body: <p>I am making a GPS system for a game, which will allow you to pick the shortest path between two point on the roads.</p>
  
  <p>As for now I hae made a class which looks as follows:</p>
  
  <pre><code>#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;
  
  using namespace boost;
  using namespace std;
  
  class GPS
  {
  public:
      typedef         boost::property&lt;boost::edge_weight_t, float&gt;                        Distance;
      typedef         adjacency_list&lt;vecS, vecS, directedS, boost::no_property, Distance&gt; Graph;
      typedef         int                                                                 Node;
      typedef         std::pair&lt;int, int&gt;                                                 Edge;
      typedef         property_map&lt;Graph, edge_weight_t&gt;::type                            weightmap_t;                
      typedef         graph_traits &lt; Graph &gt;::vertex_descriptor                           vertex_descriptor;
      typedef         graph_traits &lt; Graph &gt;::edge_descriptor                             edge_descriptor;
  private:
      vector&lt;Edge&gt;                            Edges;
      Graph                                   Nodes;
  public:
      GPS() 
      {
  
      }
      ~GPS()
      {
  
      }
      //returns amount of edges added: 0, 1 or 2
      char AddEdge(Node from, Node to, Distance weight = 0.0f, bool BothDirections = false)
      {
          char added = 0;
          if(add_edge(from,to,weight,Nodes).second)
              ++added;
          if(BothDirections)
          {
              if(add_edge(to,from,weight,Nodes).second)
                  ++added;
          }
          return added;
      }
      //returns the added node, 
      //specify your own vertex identificator if wanted 
      //(for maintaining backwards compatibility with old graphs saved in gps.dat files)
      Node AddNode(int id = -1)
      {
          if(id == -1)
              return add_vertex(Nodes);
          else
              return vertex(id,Nodes);
      }
      //get the shortest path between 'from' and 'to' by adding all nodes which are traversed into &amp;path
      void Path(Node from, Node to, vector&lt;Node&gt; &amp;path)
      {
          std::vector&lt;vertex_descriptor&gt; p(num_vertices(Nodes));
          std::vector&lt;int&gt; d(num_vertices(Nodes));
          weightmap_t weightmap = get(edge_weight, Nodes);
          vertex_descriptor s = vertex(from, Nodes);
          dijkstra_shortest_paths(Nodes, s, predecessor_map(&amp;p[0]).distance_map(&amp;d[0]));
  
          //what here? and are there faster algorithms in boost graph than dijkstra (except A*)?
      }
  };
  </code></pre>
  
  <p>Now I am really stuck when it gets to finding the path between two vertices.</p>
  
  <p>I looked up the <a href="http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/dijkstra_shortest_paths.html" rel="nofollow">documentation</a> and <a href="http://www.boost.org/doc/libs/1_38_0/libs/graph/example/dijkstra-example.cpp" rel="nofollow">example</a> for dijkstra but I just don't get it..</p>
  
  <p>Any other algorithms seem harder to setup.</p>
  
  <p>How can I find the shortest path? All the parameters and functions and stuff is very confusing.. I want to switch to boost, get away from "my own home-cooked and slow" libraries..</p>