如何找到BGL图中两个顶点之间的最短路径？ [英] How to find the shortest path between two vertices in a BGL graph?

问题描述

因此，我目前正在研究一个词梯问题的项目，并且我已经构建了用于存储所有词典词汇的图表，并在其中添加了边界，我使用boost图表库进行了此操作。

但是让我困惑的是 breadth_first_search（）函数，看起来参数只是起始顶点而没有结束顶点。

我检查了文档并注意到我可以为该搜索功能定义BFS访问者，但由于我是boost库的新手，我无法弄清楚它可以。

任何人都可以解释如何实现找到两个顶点之间的最短路径吗？

  #include >我使用的是无向图和未加权图。 // std :: cout 
 #include< fstream> 
 #include< string> 
 #include< stdlib.h> 
 #include< utility> // std :: pair 
 #includeheaders.h
 #include< boost / graph / adjacency_list.hpp> 
 #include< boost / graph / dijkstra_shortest_paths.hpp> 
 #include< boost / graph / graph_utility.hpp> 
 
使用namespace std; 
 
 //定义一个有你想要关联到每个顶点和
边的数据的类
 // struct Vertex {int foo;} 
 // struct Edge {std :: string blah;} 
 
 struct VertexProperties {
 string name; 
 VertexProperties（string name）：name（name）{} 
}; 
 
 // typedef属性< edge_weight_t，int> EdgeWeightProperty; 
 // typedef属性< vertex_name_t，string> VertexNameProperty; 
 
 //使用这些类定义图形
 typedef boost :: adjacency_list< boost :: setS，boost :: listS，boost :: undirectedS，
 VertexProperties>图形; 
 typedef Graph :: vertex_iterator Vit; 
 typedef Graph :: vertex_descriptor Vde; 
 typedef Graph :: edge_descriptor E; 
 typedef boost :: graph_traits<图表> :: adjacency_iterator adjacency_it; 
 
 
 struct my_visitor：boost :: default_dijkstra_visitor {
 using base = boost :: default_dijkstra_visitor; 
 struct done {}; 
 
 my_visitor（Vde vd，size_t& visited）：destination（vd），visited（visited）{} 
 
 void finish_vertex（Vde v，Graph const& g）{
 ++造访过; 
 
 if（v ==目标）
 throw done {}; 
 
 base :: finish_vertex（v，g）; 
} 
 
私人：
 Vde目的地; 
 size_t& visited; 
}; 
 
 //简单的一些typedef 
 // typedef boost :: graph_traits< Graph> :: vertex_descriptor vertex_t; 
 // typedef boost :: graph_traits< Graph> :: edge_descriptor edge_t; 
 int main（）
 {
 ifstream dictionary（dictionary.txt）; 
字符串字; 
图表allWords; 
 // Vit开始，结束; （字典，字））
 
 if（dictionary.is_open（））
 {
 while（getline（dictionary，word））
 {
 word.pop_back（）; 
 add_vertex（VertexProperties（word），allWords）; 
} 
} 
 else 
 cout<<文件打开失败。<< endl; 
 
 dictionary.close（）; 
 // cout<< num_vertices（allWords）<< endl; 
 Vit开始，结束; 
 boost :: tie（begin，end）= vertices（allWords）; 
 
 vector< Graph :: vertex_descriptor> vindex（开始，结束）; 
 
 int first = 0; 
 int second = 0; 
 for（Vit it = begin; it！= end; it ++）
 {
 for（Vit that = it; that！= end; that ++）
 {
 if（isEditDistanceOne（allWords [* it] .name，allWords [* that] .name））
 add_edge（vindex [first]，vindex [second]，allWords）; 
秒++; 
} 
第一个++; 
 second = first; 
 cout<< first<< endl; 
} 
 // Vit temp = begin; 
 // temp ++; 
 //cout<<allWords[*begin].name<<\"////////////////\"<<endl; 
 adjacency_it neighbor，neighbour_end; 
 for（tie（neighbor，neighbour_end）= adjacent_vertices（* begin，allWords）; 
 neighbor！= neighbour_end; ++ neighbor）
 cout <<< allWords [* neighbor] .name< < ENDL; 
 
 
 
字符串firstWord; 
字符串secondWord; 
 
 int firstIndex = -1; 
 int secondIndex = -1; 
 
 cout<<输入第一个字：<< endl; 
 cin>> firstWord; 
 
 cout<<输入第二个字：<< endl; 
 cin>> secondWord; 
 
 
 Vit a = begin; 
 for（int i = 0; i< num_vertices（allWords）; i ++）
 {
 if（allWords [* a] .name == firstWord）
 {
 firstIndex = i; 
休息; 
} 
 a ++; 
} 
 
 Vit b = begin; 
 for（int i = 0; i< num_vertices（allWords）; i ++）
 {
 if（allWords [* b] .name == secondWord）
 {
 secondIndex = i; 
休息; 
} 
 b ++; 
} 
 
 if（firstIndex == -1）
 cout <<<第一个字词不在图表中。<< endl; 
 
 else if（secondIndex == -1）
 cout <<<第二个字不在图中。<< endl; 
 
 else 
 {
 Vde start_vertex = vindex [firstIndex]; 
 Vde end_vertex = vindex [secondIndex]; 
 
 size_t visited; 
 std :: vector< boost :: default_color_type>颜色（num_vertices（allWords），
 boost :: default_color_type {}）; 
 std :: vector< Vde> _pred（num_vertices（allWords），
 allWords.null_vertex（））; 
 std :: vector< size_t> _dist（num_vertices（allWords），
 -lull）; 
 
 my_visitor vis {end_vertex，visited}; 
 auto predmap = _pred.data（）; //内部属性：
 boost :: get（boost :: vertex_predecessor，g）; 
 auto distmap = _dist.data（）; //内部属性：
 boost :: get（boost :: vertex_distance，g）; 
 
尝试{
 std :: cout<< 从＃开始搜索<< start_vertex<< to＃<< end_vertex 
<< 
... \\\
; 
 boost :: dijkstra_shortest_paths（allWords，start_vertex，
 boost :: visitor（vis）。
 color_map（colors.data（））。
 distance_map（distmap）。
 predecessor_map（predmap）。
 weight_map（boost :: make_constant_property< E>（1ul））
）; 
 
 std :: cout<< 找不到路径。 
返回0; 
} catch（my_visitor :: done const&）{
 std :: cout<< 跳过的百分比：<< 
（100.0 * visited / num_vertices（allWords））<< ％\\\
; 
} 
} 
 
 
 // cout<<< adjacency_list [* begin]<<\t; 
返回0; 
 
  

解决方案

发现你的目标。

这里有一个工作示例

Live Live Coliru

  #include< boost / graph / adjacency_list.hpp> 
 #include< boost / graph / graph_utility.hpp> 
 #include< boost / graph / dijkstra_shortest_paths.hpp> 
 #include< boost / graph / random.hpp> 
 #include< random> 
 #include< iostream> 
 
使用G = boost :: adjacency_list< boost :: vecS，boost :: vecS，boost :: undirectedS>; 
使用V = G :: vertex_descriptor; 
使用E = G :: edge_descriptor; 
 
 struct my_visitor：boost :: default_dijkstra_visitor {
 using base = boost :: default_dijkstra_visitor; 
 struct done {}; 
 
 my_visitor（V vd，size_t& visited）：destination（vd），visited（visited）{} 
 
 void finish_vertex（V v，G const& g）{
 ++造访过; 
 
 if（v ==目标）
 throw done {}; 
 
 base :: finish_vertex（v，g）; 
} 
 
私人：
 V目的地; 
 size_t& visited; 
}; 
 
 int main（）{
 #if 1 
 auto seed = 2912287549; //修改种子
 #else 
 auto seed = std :: random_device {}（）; 
 std :: cout<< SEED：<<种子 \\\
; 
 #endif 
 std :: mt19937 prng {seed}; 
 G g; 
 generate_random_graph（g，100，400，prng）; 
 print_graph（g）; 
 
 V start_vertex = prng（）％num_vertices（g）; 
 V end_vertex = prng（）％num_vertices（g）; 
 
 size_t visited; 
 std :: vector< boost :: default_color_type>颜色（num_vertices（g），boost :: default_color_type {}）; 
 std :: vector< V> _pred（num_vertices（g），g.null_vertex（））; 
 std :: vector< size_t> _dist（num_vertices（g），-1ull）; 
 
 my_visitor vis {end_vertex，visited}; 
 auto predmap = _pred.data（）; //内部属性：boost :: get（boost :: vertex_predecessor，g）; 
 auto distmap = _dist.data（）; //内部属性：boost :: get（boost :: vertex_distance，g）; 
 
尝试{
 std :: cout<< 从＃开始搜索<< start_vertex<< to＃<< end_vertex<< ...... \\\
; 
 boost :: dijkstra_shortest_paths（g，start_vertex，
 boost :: visitor（vis）。
 color_map（colors.data（））。
 distance_map（distmap）。
 predecessor_map（predmap）。
 weight_map（boost :: make_constant_property< E>（1ul））
）; 
 
 std :: cout<< 找不到路径。 
返回0; 
} catch（my_visitor :: done const&）{
 std :: cout<< 跳过的百分比：<< （100.0 * visited / num_vertices（g））<< ％\\\
; 
} 
 
 size_t distance = distmap [end_vertex]; 
 std :: cout<< 与＃的距离<< start_vertex<< to＃<< end_vertex<< ：<<距离<< \\\
; 
 
 if（distance！= size_t（-1））{
 std :: deque< V>路径; 
 for（V current = end_vertex; 
 current！= g.null_vertex（）
&& predmap [current]！= current 
&& current！= start_vertex ;）
 {
 path.push_front（predmap [current]）; 
 current = predmap [current]; 
} 
 
 std :: cout<< 来自＃的路径<< start_vertex<< to＃<< end_vertex<< ：; 
 std :: copy（path.begin（），path.end（），std :: ostream_iterator< V>（std :: cout，，））; 
 std :: cout<< end_vertex<< \\\
; 
 
 
 
 
 $ b $ p 
 $ b 
它会生成100个顶点和400个边的随机无向图。 
对于特定的演示种子，它会输出以下输出： 
 
 
  0  - <  - > 45 46 15 83 69 32 38 68 37 
 1  - <  - > 29 52 99 85 10 19 30 78 
 2  -   -   - 42 7 35 80 25 9 23 23 
 3  -   -   - 29 9 15 77 7 58 42 
 4  - <  - > 75 56 98 24 14 40 97 34 84 37 80 30 62 
 5  - 58 46 80 71 
 6  - <  - > 89 12 47 88 80 
 7  - < 62 69 2 86 88 74 8 33 13 76 3 9 86 48 
 8  -   -   - 64 26 31 7 94 95 77 
 9  - <  - > 83 53 76 3 43 55 7 2 67 72 
 10  -   -   - 51 16 21 20 1 63 31 
 11  -   -   - 38 50 19 88 16 52 
 12  -   - 46 6 85 21 61 39 
 13  -   -   - 95 24 17 51 7 
 14  -   - 24 4 43 53 
 15  -   - > 0 51 70 3 43 34 
 16  - <  - > 72 10 23 99 28 35 22 11 96 99 19 38 39 
 17  -   -   - 84 25 13 54 74 96 28 
 18  -   -   - 90 54 88 78 
 19  -   -   - 63 11 61 20 73 22 1 63 90 75 16 
 20  -   -   - 70 57 79 35 19 10 65 79 45 
 21  -   -   - 49 89 43 50 10 38 12 26 67 
 22  -   -   - 41 49 95 99 25 39 23 16 19 81 
 23  - 35 16 22 95 2 69 2 
 24  - 76 85 13 42 14 4 85 88 
 25  - 98 17 22 72 92 60 2 51 
 26  -   -   - 65 48 62 8 50 86 44 37 21 48 
 27  -   -   - 42 82 
 28  -   - 92 46 89 16 50 53 59 17 94 
 29  - 1 33 3 46 91 96 46 48 
 30  -   -   - 60 96 70 79 1 48 4 
 31  -   -   - 37 66 50 8 59 72 32 87 10 67 
 32  -   -   - 84 77 49 71 0 31 81 75 98 66 
 33  - 29 83 66 7 69 74 80 79 
 34  - 90 59 73 61 47 4 75 87 15 
 35  - 51 23 46 20 16 2 68 
 36  - 70 
 37  -   - 31 41 77 68 70 26 70 4 0 60 
 38  -   -   - 11 65 74 0 21 39 50 94 16 86 
 39  -   -   - 48 88 38 22 12 89 16 
 40  -   -   - 81 92 86 4 55 
 41  - <  - > 22 37 74 64 63 63 79 
 42  -   -   - 27 2 24 84 90 65 67 76 72 93 3 
 43  -   -   - 51 75 21 54 9 65 14 53 44 15 
 44  -   -   - 74 82 26 43 
 45  -   - 0 86 70 46 94 89 20 
 46  -   - 0 12 28 35 45 96 5 29 29 
 47  -   -   - 96 51 6 82 62 34 88 78 
 48  -   -   - 26 99 39 50 59 78 30 29 7 26 
 49  -   -   - 21 22 52 32 99 61 55 69 66 57 
 50  -   -   - 82 11 31 21 26 65 28 48 38 94 55 
 51  -   -   - 43 35 10 47 15 55 13 55 88 25 69 84 
 52  - 86 49 66 1 93 55 11 74 90 
 53  - 89 76 9 76 82 28 77 43 14 
 54  -   - 87 43 17 98 59 18 66 
 55  -   -   - 68 76 51 65 51 81 52 9 49 92 50 40 
 56  -   -   - 4 82 95 88 80 
 57  - < 20 87 66 62 49 
 58  -   - 5 3 
 59  - <  - > 34 75 71 28 31 48 54 70 96 
 60  -   - 81 30 81 87 61 61 25 37 
 61  - <  - > 78 62 97 19 49 34 12 60 60 
 62  -   -   - 7 26 69 87 61 70 92 57 47 90 4 
 63  - <  - > 19 41 41 10 72 19 
 64  - <  - > 8 92 41 95 86 
 65  -   - 26 38 50 42 55 43 83 79 20 79 
 66  - <  - > 52 31 33 57 87 54 32 49 
 67  -   -   - 97 42 98 9 31 21 
 68  -   - 55 74 96 37 0 98 35 
 69  -   - 7 97 62 0 97 33 70 49 75 51 23 
 70  -   -   - 20 83 45 78 15 69 30 37 62 37 59 78 77 36 
 71  -   -   - 83 74 59 32 5 88 
 72  -   -   - 16 74 31 25 85 83 42 63 9 
 73  -   -   - 74 34 87 19 
 74  - <  - > 68 73 41 44 72 71 7 38 17 96 33 82 52 
 75  - 4 43 59 86 32 34 19 69 85 
 76  -   - 24 53 55 53 9 42 7 
 77  -   -   - 32 37 79 53 3 70 96 90 8 
 78  -   -   - 61 70 70 48 1 18 47 
 79  -   - 20 77 41 30 98 65 20 33 65 82 
 80  -   -   - 82 81 86 93 56 5 33 2 6 4 
 81  -   -   - 40 60 60 80 91 55 32 22 
 82  - < 80 50 44 56 88 53 47 27 74 79 
 83  -   - 9 70 71 0 33 95 72 65 
 84  -   -   - 32 17 42 86 4 51 
 85  - 24 96 12 87 24 1 72 89 87 75 
 86  - <  - > 52 45 40 7 84 26 75 80 7 64 38 
 87  -   -   - 54 57 73 85 62 60 66 31 85 34 
 88  -   -   - 7 39 82 56 11 6 51 24 18 47 71 
 89  -   -   - 53 21 6 28 99 92 45 85 39 
 90  -   -   - 34 42 96 18 77 19 62 52 
 91  -   -   - 81 29 
 92  -   - > 28 40 64 62 25 89 55 
 93  -   - 52 80 42 
 94  - <  - > 8 45 50 28 38 
 95  -   -   - 22 13 83 56 23 64 8 
 96  - <  - > 85 47 30 68 46 90 74 17 16 77 29 59 
 97  -   -   - 69 67 61 69 4 
 98  - <  - > 25 4 54 79 68 67 32 
 99  - > 22 48 16 89 1 49 16 
从＃20到＃27搜索... 
跳过的百分比：91％
从＃20到＃27的距离：3 
从＃ 20到＃27：20，65，42，27 
  
正如您所看到的，91％的节点没有被访问过。 
 
 
注意事项
 
 
 
文档说在边缘权重为不变。我不能悲伤地做这件事。
 
 
 
假设算法等价性被断言，路径仍然会使用提前（尽管边缘权重是常量）。
 
So I'm currently working on a project of a word ladder problem and I have already built the graph for storing all dictionary words in it and added the edges in it, I did this using boost graph library.

But what is confusing me is that breadth_first_search() function, seems like the parameters only take the starting vertex but no ending vertex. 

I checked the documentations and noticed that I can define the BFS visitor for that search function, but since I'm a newbie to the boost library I could not figure out how it works.

Can anybody explain how to implement finding the shortest path between two vertices? I'm using an undirected and unweighted graph.
#include <iostream> // std::cout
#include <fstream>
#include <string>
#include <stdlib.h>
#include <utility> // std::pair
#include "headers.h"
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>

using namespace std;

//Define a class that has the data you want to associate to every vertex and 
edge
//struct Vertex{ int foo;}
//  struct Edge{std::string blah;}

struct VertexProperties {
  string name;
  VertexProperties(string name) : name(name) {}
};

//typedef property<edge_weight_t, int> EdgeWeightProperty;
//typedef property<vertex_name_t, string> VertexNameProperty;

//Define the graph using those classes
typedef boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, 
VertexProperties> Graph;
typedef Graph::vertex_iterator Vit;
typedef Graph::vertex_descriptor Vde;
typedef Graph::edge_descriptor E;
typedef boost::graph_traits<Graph>::adjacency_iterator adjacency_it;


struct my_visitor : boost::default_dijkstra_visitor {
 using base = boost::default_dijkstra_visitor;
 struct done{};

my_visitor(Vde vd, size_t& visited) : destination(vd), visited(visited) {}

void finish_vertex(Vde v, Graph const& g) {
++visited;

if (v == destination)
  throw done{};

base::finish_vertex(v, g);
}

private:
Vde destination;
size_t &visited;
};

//Some typedefs for simplicity
//typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
//typedef boost::graph_traits<Graph>::edge_descriptor edge_t;
int main()
{
ifstream dictionary("dictionary.txt");
string word;
Graph allWords;
//Vit begin,end;

if(dictionary.is_open())
{
  while(getline(dictionary,word))
    {
  word.pop_back();
      add_vertex(VertexProperties(word),allWords);
    }
 }
else 
cout<<"File openning failed."<<endl;

dictionary.close();
//cout<<num_vertices(allWords)<<endl;
Vit begin,end;
boost::tie(begin, end) = vertices(allWords);

vector<Graph::vertex_descriptor> vindex(begin, end);

int first=0;
int second=0;
for(Vit it=begin;it!=end;it++)
{
  for(Vit that=it;that!=end;that++)
    {
      if(isEditDistanceOne(allWords[*it].name,allWords[*that].name))
        add_edge(vindex[first],vindex[second],allWords);
      second++;
    }
  first++;
  second=first;
  cout<<first<<endl;
 }
//Vit temp=begin;
//temp++;   
//cout<<allWords[*begin].name<<"////////////////"<<endl;
adjacency_it neighbour, neighbour_end;
for (tie(neighbour, neighbour_end) = adjacent_vertices(*begin, allWords); 
    neighbour != neighbour_end; ++neighbour)
cout<<allWords[*neighbour].name<<endl;



string firstWord;
string secondWord;

int firstIndex=-1;
int secondIndex=-1;

cout<<"Enter first word:"<<endl;
cin>>firstWord;

cout<<"Enter second word:"<<endl;
cin>>secondWord;


Vit a=begin;
for(int i=0;i<num_vertices(allWords);i++)
{
  if(allWords[*a].name==firstWord)
    {
      firstIndex=i;
      break;
    }
  a++;
}

Vit b=begin;
for(int i=0;i<num_vertices(allWords);i++)
{
  if(allWords[*b].name==secondWord)
    {
      secondIndex=i;
      break;
    }
  b++;
}

if(firstIndex==-1)
  cout<<"First word not in graph."<<endl;

else if(secondIndex==-1)
  cout<<"Second word not in graph."<<endl;

else
{
  Vde start_vertex=vindex[firstIndex];
  Vde end_vertex=vindex[secondIndex];

  size_t visited;
  std::vector<boost::default_color_type> colors(num_vertices(allWords), 
  boost::default_color_type{});
  std::vector<Vde>                         _pred(num_vertices(allWords),   
  allWords.null_vertex());
  std::vector<size_t>                    _dist(num_vertices(allWords),   
  -1ull);

  my_visitor vis { end_vertex, visited };
  auto predmap = _pred.data(); // interior properties: 
  boost::get(boost::vertex_predecessor, g);
  auto distmap = _dist.data(); // interior properties: 
  boost::get(boost::vertex_distance, g);

  try {
  std::cout << "Searching from #" << start_vertex << " to #" << end_vertex 
  << 
  "...\n";
  boost::dijkstra_shortest_paths(allWords, start_vertex, 
                   boost::visitor(vis).
                   color_map(colors.data()).
                   distance_map(distmap).
                   predecessor_map(predmap).
                   weight_map(boost::make_constant_property<E>(1ul))
                   );

  std::cout << "No path found\n";
    return 0;
  } catch(my_visitor::done const&) {
  std::cout << "Percentage skipped: " << 
 (100.0*visited/num_vertices(allWords)) << "%\n";
  } 
 }


 //cout<<adjacency_list[*begin]<<"\t";
 return 0;
 }

解决方案
Just abort the search when you discover your target.

Here's a working sample

Live On Coliru
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/random.hpp>
#include <random>
#include <iostream>

using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
using V = G::vertex_descriptor;
using E = G::edge_descriptor;

struct my_visitor : boost::default_dijkstra_visitor {
    using base = boost::default_dijkstra_visitor;
    struct done{};

    my_visitor(V vd, size_t& visited) : destination(vd), visited(visited) {}

    void finish_vertex(V v, G const& g) {
        ++visited;

        if (v == destination)
            throw done{};

        base::finish_vertex(v, g);
    }

  private:
    V destination;
    size_t &visited;
};

int main() {
#if 1
    auto seed = 2912287549; // fixed seed for demo
#else
    auto seed = std::random_device{}();
    std::cout << "SEED: " << seed << "\n";
#endif
    std::mt19937 prng { seed };
    G g;
    generate_random_graph(g, 100, 400, prng);
    print_graph(g);

    V start_vertex = prng()%num_vertices(g);
    V end_vertex   = prng()%num_vertices(g);

    size_t visited;
    std::vector<boost::default_color_type> colors(num_vertices(g), boost::default_color_type{});
    std::vector<V>                         _pred(num_vertices(g),   g.null_vertex());
    std::vector<size_t>                    _dist(num_vertices(g),   -1ull);

    my_visitor vis { end_vertex, visited };
    auto predmap = _pred.data(); // interior properties: boost::get(boost::vertex_predecessor, g);
    auto distmap = _dist.data(); // interior properties: boost::get(boost::vertex_distance, g);

    try {
        std::cout << "Searching from #" << start_vertex << " to #" << end_vertex << "...\n";
        boost::dijkstra_shortest_paths(g, start_vertex, 
                boost::visitor(vis).
                color_map(colors.data()).
                distance_map(distmap).
                predecessor_map(predmap).
                weight_map(boost::make_constant_property<E>(1ul))
            );

        std::cout << "No path found\n";
        return 0;
    } catch(my_visitor::done const&) {
        std::cout << "Percentage skipped: " << (100.0*visited/num_vertices(g)) << "%\n";
    }

    size_t distance = distmap[end_vertex];
    std::cout << "Distance from #" << start_vertex << " to #" << end_vertex << ": " << distance << "\n";

    if (distance != size_t(-1)) {
        std::deque<V> path;
        for (V current = end_vertex; 
                current != g.null_vertex() 
                && predmap[current] != current 
                && current != start_vertex;) 
        {
            path.push_front(predmap[current]);
            current = predmap[current];
        }

        std::cout << "Path from #" << start_vertex << " to #" << end_vertex << ": ";
        std::copy(path.begin(), path.end(), std::ostream_iterator<V>(std::cout, ", "));
        std::cout << end_vertex << "\n";
    }
}
It generates random undirected graphs with 100 vertices and 400 edges.
For the specific demo seed it prints the following output:
0 <--> 45 46 15 83 69 32 38 68 37 
1 <--> 29 52 99 85 10 19 30 78 
2 <--> 42 7 35 80 25 9 23 23 
3 <--> 29 9 15 77 7 58 42 
4 <--> 75 56 98 24 14 40 97 34 84 37 80 30 62 
5 <--> 58 46 80 71 
6 <--> 89 12 47 88 80 
7 <--> 62 69 2 86 88 74 8 33 13 76 3 9 86 48 
8 <--> 64 26 31 7 94 95 77 
9 <--> 83 53 76 3 43 55 7 2 67 72 
10 <--> 51 16 21 20 1 63 31 
11 <--> 38 50 19 88 16 52 
12 <--> 46 6 85 21 61 39 
13 <--> 95 24 17 51 7 
14 <--> 24 4 43 53 
15 <--> 0 51 70 3 43 34 
16 <--> 72 10 23 99 28 35 22 11 96 99 19 38 39 
17 <--> 84 25 13 54 74 96 28 
18 <--> 90 54 88 78 
19 <--> 63 11 61 20 73 22 1 63 90 75 16 
20 <--> 70 57 79 35 19 10 65 79 45 
21 <--> 49 89 43 50 10 38 12 26 67 
22 <--> 41 49 95 99 25 39 23 16 19 81 
23 <--> 35 16 22 95 2 69 2 
24 <--> 76 85 13 42 14 4 85 88 
25 <--> 98 17 22 72 92 60 2 51 
26 <--> 65 48 62 8 50 86 44 37 21 48 
27 <--> 42 82 
28 <--> 92 46 89 16 50 53 59 17 94 
29 <--> 1 33 3 46 91 96 46 48 
30 <--> 60 96 70 79 1 48 4 
31 <--> 37 66 50 8 59 72 32 87 10 67 
32 <--> 84 77 49 71 0 31 81 75 98 66 
33 <--> 29 83 66 7 69 74 80 79 
34 <--> 90 59 73 61 47 4 75 87 15 
35 <--> 51 23 46 20 16 2 68 
36 <--> 70 
37 <--> 31 41 77 68 70 26 70 4 0 60 
38 <--> 11 65 74 0 21 39 50 94 16 86 
39 <--> 48 88 38 22 12 89 16 
40 <--> 81 92 86 4 55 
41 <--> 22 37 74 64 63 63 79 
42 <--> 27 2 24 84 90 65 67 76 72 93 3 
43 <--> 51 75 21 54 9 65 14 53 44 15 
44 <--> 74 82 26 43 
45 <--> 0 86 70 46 94 89 20 
46 <--> 0 12 28 35 45 96 5 29 29 
47 <--> 96 51 6 82 62 34 88 78 
48 <--> 26 99 39 50 59 78 30 29 7 26 
49 <--> 21 22 52 32 99 61 55 69 66 57 
50 <--> 82 11 31 21 26 65 28 48 38 94 55 
51 <--> 43 35 10 47 15 55 13 55 88 25 69 84 
52 <--> 86 49 66 1 93 55 11 74 90 
53 <--> 89 76 9 76 82 28 77 43 14 
54 <--> 87 43 17 98 59 18 66 
55 <--> 68 76 51 65 51 81 52 9 49 92 50 40 
56 <--> 4 82 95 88 80 
57 <--> 20 87 66 62 49 
58 <--> 5 3 
59 <--> 34 75 71 28 31 48 54 70 96 
60 <--> 81 30 81 87 61 61 25 37 
61 <--> 78 62 97 19 49 34 12 60 60 
62 <--> 7 26 69 87 61 70 92 57 47 90 4 
63 <--> 19 41 41 10 72 19 
64 <--> 8 92 41 95 86 
65 <--> 26 38 50 42 55 43 83 79 20 79 
66 <--> 52 31 33 57 87 54 32 49 
67 <--> 97 42 98 9 31 21 
68 <--> 55 74 96 37 0 98 35 
69 <--> 7 97 62 0 97 33 70 49 75 51 23 
70 <--> 20 83 45 78 15 69 30 37 62 37 59 78 77 36 
71 <--> 83 74 59 32 5 88 
72 <--> 16 74 31 25 85 83 42 63 9 
73 <--> 74 34 87 19 
74 <--> 68 73 41 44 72 71 7 38 17 96 33 82 52 
75 <--> 4 43 59 86 32 34 19 69 85 
76 <--> 24 53 55 53 9 42 7 
77 <--> 32 37 79 53 3 70 96 90 8 
78 <--> 61 70 70 48 1 18 47 
79 <--> 20 77 41 30 98 65 20 33 65 82 
80 <--> 82 81 86 93 56 5 33 2 6 4 
81 <--> 40 60 60 80 91 55 32 22 
82 <--> 80 50 44 56 88 53 47 27 74 79 
83 <--> 9 70 71 0 33 95 72 65 
84 <--> 32 17 42 86 4 51 
85 <--> 24 96 12 87 24 1 72 89 87 75 
86 <--> 52 45 40 7 84 26 75 80 7 64 38 
87 <--> 54 57 73 85 62 60 66 31 85 34 
88 <--> 7 39 82 56 11 6 51 24 18 47 71 
89 <--> 53 21 6 28 99 92 45 85 39 
90 <--> 34 42 96 18 77 19 62 52 
91 <--> 81 29 
92 <--> 28 40 64 62 25 89 55 
93 <--> 52 80 42 
94 <--> 8 45 50 28 38 
95 <--> 22 13 83 56 23 64 8 
96 <--> 85 47 30 68 46 90 74 17 16 77 29 59 
97 <--> 69 67 61 69 4 
98 <--> 25 4 54 79 68 67 32 
99 <--> 22 48 16 89 1 49 16 
Searching from #20 to #27...
Percentage skipped: 91%
Distance from #20 to #27: 3
Path from #20 to #27: 20, 65, 42, 27
As you can see, 91% of nodes weren't visited.

Notes

The docs say to use breadth-first search when the edge weight is constant. I couldn't make that work sadly.

Assuming that algorithmic equivalence is asserted, the paths will still be shortest using the early-out (assuming that the edge weight is constant).

                        
这篇关于如何找到BGL图中两个顶点之间的最短路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！