本文介绍了如何找到BGL图中两个顶点之间的最短路径？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
因此，我目前正在研究一个词梯问题的项目，并且我已经构建了用于存储所有词典词汇的图表，并在其中添加了边界，我使用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, 27As you can see, 91% of nodes weren't visited.
NotesThe 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图中两个顶点之间的最短路径？
发布评论