Home>

Hello everyone! There is a non-oriented unbelievable graph ... I want to find the shortest path between the two vertices ... I understand you need to use the algorithm search in width ... For solving the problem, I use Boost BGL ... The Breadth _first Search, and that this algorithm searches for the shortest path, you need to write a class visitor who is inherited from Boost :: Default < em>_ bfs ____ Visitor ... How to implement this class to show the shortest path between the two vertices? Send an example or link to any article or book (not "c++ Boost Graph Library only. Programmer's library")!

  • Answer # 1

    And what didn't you please the book "c++ Boost Graph Library. Library of a programmer"? There may be everything very confused at first glance, but if it is a little tinker, then things become clearer. Also, in my opinion, there is very good Wiki.By BGL, once even used her. So, in this documentation there is an example of the application of a visitor inherited from Default_dfs_visitor -BreadthfirstSearch.cpp

    #include &lt;
    Boost /Graph /Adjacency_List.HPP &GT;
    #Include &lt;
    Boost /Graph /Breadth_First_Search.HPP &GT;
    #Include &lt;
    iostream &gt;
    //That the most visitor who simply prints the order of making the vertices in the column
    Class Custom_Bfs_Visitor: Public Boost :: Default_Bfs_Visitor
    {
    Public:
      //Print here
      Template &lt;
     TYPENAME VERTEX, TYPENAME GRAPH &GT;
      Void Discover_Vertex (Vertex U, Const Graph &
     G) Const.
      {
        STD :: COUT &LT;
    &Lt;
     U &LT;
    &Lt;
     STD :: ENDL;
      }
    };
    INT MAIN ()
    {
      TypeDef Boost :: Adjacency_List &LT;
     Boost :: VECS, BOOST :: VECS, BOOST :: Undirecteds &gt;
     graph_t; //Graf type
      graph_t g; //Graf himself
      add_edge (0, 1, g); //Adding Roeber to Count
      add_edge (0, 2, g);
      add_edge (1, 3, g);
      add_edge (0, 4, g);
      Custom_BFS_VISITOR VIS; //Our visitor
      Breadth_First_Search (G, Vertex (0, G), Visitor (VIS)); //Calling a width search function
      //The output must be 0 1 2 4 3
      Return EXIT_SUCCESS;
    }
    

    I once again helped on this forum well, so you can.