采用boost graph 获取两节点间的路径
时间: 2024-01-06 22:05:45 浏览: 25
要获取两节点间的路径,可以使用boost graph库中的dijkstra_shortest_paths算法。以下是一个简单的示例代码:
```c++
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
using namespace boost;
int main()
{
typedef adjacency_list<vecS, vecS, directedS,
no_property, property<edge_weight_t, int> > Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef std::pair<int,int> Edge;
const int num_vertices = 5;
enum { A, B, C, D, E };
char name[] = "ABCDE";
Edge edge_array[] = { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
Edge(C,E), Edge(B,D), Edge(D,E) };
int weights[] = { 1, 2, 3, 4, 1, 2, 1 };
int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);
Graph g(edge_array, edge_array + num_edges, weights, num_vertices);
property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g);
std::vector<Vertex> predecessors(num_vertices);
std::vector<int> distances(num_vertices);
// Run Dijkstra's algorithm starting from vertex A
Vertex start = vertex(A, g);
dijkstra_shortest_paths(g, start,
predecessor_map(&predecessors[0]).distance_map(&distances[0]));
// Print the shortest path from A to E
std::cout << "Shortest path from A to E:" << std::endl;
for(Vertex v = vertex(E, g); v != start; v = predecessors[v])
std::cout << name[v] << " <- ";
std::cout << name[start] << std::endl;
return 0;
}
```
在上面的示例代码中,我们创建了一个有向图,并使用dijkstra_shortest_paths算法从节点A开始查找到节点E的最短路径。可以根据需要更改节点和边的数量和权重,以适应实际应用场景。