1 #include <iostream>
2 #include <
string>
3 #include <utility>
4 #include <vector>
5 #include <deque>
6 #include <boost/graph/adjacency_list.hpp>
7 //A*寻路算法
8 #include <boost\graph\astar_search.hpp>
9 using namespace std;
10 using namespace boost;
11
12 enum { A, B, C, D, E, N };
13 string Names =
"ABCDE";
14 //定义别名,两个顶点直接连接的边
15 using Edge = pair<
int,
int>
;
16 //创建一个图 边 顶点 有方向 无特性 边的权重是int
17 using Graph = adjacency_list<listS, vecS, directedS, no_property, property<edge_weight_t,
int>>
;
18
19 //创建一个图
20 Graph make_graph()
21 {
22 //连接的边
23 vector<Edge> edges =
{ {A,B},
24 {A,C},
25 {A,D},
26 {B,E},{C,E},{D,E} };
27 //边对应的权重
28 vector<
int> weight = {
3,
1,
4,
5,
2,
6 };
29
30 //创建一个图对象
31 return Graph(edges.begin(), edges.end(), weight.begin(), N);
32 }
33
34 //创建一个结构体,用于抛出找到信息
35 struct found_goal
36 {
37
38 };
39
40 //A*要到达的目标顶点
41 template<
class vertex>
42 class astar_my_visitor :
public boost::default_astar_visitor
43 {
44 public:
45 //初始化内置地图
46 astar_my_visitor(vertex goal) :m_goal(goal)
47 {
48
49 }
50 //重载examine_vertex方法
51 template<
class Graph>
52 void examine_vertex(vertex v, Graph &
g)
53 {
54 //如果与目标顶点一样,则说明找到
55 if (v ==
m_goal)
56 {
57 //抛出抛出找到信息
58 throw found_goal();
59 }
60 }
61 private:
62 //目标顶点
63 vertex m_goal;
64 };
65
66 //计算权重寻找最短路径
67 template<
class Graph,
class costtype>
68 class distance_heuristic :
public boost::astar_heuristic<Graph, costtype>
69 {
70 public:
71 //类型替换
72 using Vertex = typename boost::graph_traits<Graph>
::vertex_descriptor;
73
74 //初始化
75 distance_heuristic(Vertex Goal, Graph &
graph):Goal_(Goal),graph_(graph)
76 {
77
78 }
79
80 //重载()运算符 获得目标点到指定点的距离
81 costtype
operator()(Vertex v)
82 {
83 return get(vertex_index, graph_, Goal_) -
get(vertex_index, graph_, v);
84 }
85
86 private:
87 Vertex Goal_;
88 Graph &
graph_;
89 };
90
91
92 void main()
93 {
94 //创建图
95 Graph myg =
make_graph();
96
97 //创建简写
98 using Vertex = boost::graph_traits<Graph>
::vertex_descriptor;
99 using Cost =
int;
100
101 Vertex start = vertex(A, myg);
//开始位置
102 Vertex goal = vertex(E, myg);
//结束位置
103
104 //保存走过路径(由后向前)
105 vector<Vertex>
parents(boost::num_vertices(myg));
106 //保存长度
107 vector<Cost>
distance(boost::num_vertices(myg));
108
109 try
110 {
111 //求从指定点到终点的路线
112
113 boost::astar_search_tree(myg,
114 start,
115 distance_heuristic<Graph, Cost>(goal, myg),
//传递距离
116
117 //求出路径，以及路径对应的权重，访问器访问 因为重载了()运算符
118 boost::predecessor_map(&parents[
0]).distance_map(&distance[
0]).visitor(astar_my_visitor<Vertex>
(goal))
119 );
120 }
121 //catch信息
122 catch (found_goal fg)
123 {
124 //要到的位置的前一个到达的位置如果是goal(下标是当前点,值是到这个点之前的点)
125 if (parents[goal] ==
goal)
126 {
127 cout <<
"无路可走" <<
endl;
128 }
129 deque<Vertex>
route;
130
131 //顺藤摸瓜
132 for (Vertex v = goal; v != start; v =
parents[v])
133 {
134 route.push_front(v);
135 }
136 for (auto i : route)
137 {
138 cout << Names[i] <<
endl;
139 }
140 }
141
142 system(
"pause");
143 }
转载于:https://www.cnblogs.com/xiaochi/p/8671740.html
相关资源：数据结构—成绩单生成器
