我正在尝试使用 BGL 中的 dijkstra 最短路径算法来计算未加权无向图上的简单 ST 路径。将来我可能会关心边权重,但现在我只想将边遍历视为统一成本。
我也在跟踪多个边和顶点属性,所以我已经基于 bundled properties example 到目前为止我所做的事情似乎最接近我正在尝试做的事情。
现在我想弄清楚如何让 dijkstra 工作,这样我就可以进行 ST 搜索,但我一直在为它设置正确的参数。
这是迄今为止我拥有的代码的简化示例:
#include <iostream>
#include <vector>
#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>
// Create a struct to hold properties for each vertex
typedef struct VertexProperties
{
int p1;
} VertexProperties;
// Create a struct to hold properties for each edge
typedef struct EdgeProperties
{
int p1;
} EdgeProperties;
// Define the type of the graph
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties> Graph;
int main(int,char*[])
{
// Create a graph object
Graph g;
// Add vertices
Graph::vertex_descriptor v0 = boost::add_vertex(g);
Graph::vertex_descriptor v1 = boost::add_vertex(g);
Graph::vertex_descriptor v2 = boost::add_vertex(g);
// Set vertex properties
g[v0].p1 = 1;
g[v1].p1 = 2;
g[v2].p1 = 3;
// Add edges
std::pair<Graph::edge_descriptor, bool> e01 = boost::add_edge(v0, v1, g);
std::pair<Graph::edge_descriptor, bool> e02 = boost::add_edge(v1, v2, g);
// Set edge properties
g[e01.first].p1 = 1;
g[e02.first].p1 = 2;
std::cout << "num_verts: " << boost::num_vertices(g) << std::endl;
std::cout << "num_edges: " << boost::num_edges(g) << std::endl;
// compute ST shortest paths here...
return 0;
}
我对调用 dijkstra 算法的正确参数感到困惑。他们采用图、起始顶点,然后是前驱图和距离图。到目前为止我看到的例子,比如 this one 只用一个边权重设置了他们的图,而没有捆绑的边属性,这简化了事情。
最终,我追求的是 ST 最短路径,所以我需要恢复从 S 到 T 的路径。从事情的角度来看,我们需要设置一个前驱 map ,然后我们可以使用它从一个路径中提取路径特别T回S?
我还应该注意,我所处的环境不允许 C++11 语言功能。 :(
这里的任何帮助将不胜感激!
最佳答案
所以问题是“如何使用捆绑属性作为 Boost Graph 库的权重图?”。
好的。您使用属性映射。捆绑属性可以在“捆绑属性”页面上使用一些时髦的语法文档访问: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/bundles.html ,请参阅标题“捆绑属性的属性映射”。
现在进行快速演示:
// set up a weight map:
auto weights = boost::get(&EdgeProperties::p1, g);
将最少数量的参数传递给 dijkstra:
// you can pass it to dijkstra using direct or named params. Let's do the simplest
boost::dijkstra_shortest_paths(g, v0, boost::no_named_parameters() .weight_map(weights));
您将想要添加更多参数,但是嘿,这是您的开始:)
Live On Coliru
#include <iostream>
#include <vector>
#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/graph_utility.hpp>
// Create a struct to hold properties for each vertex
struct VertexProperties { int p1; };
// Create a struct to hold properties for each edge
struct EdgeProperties { int p1; };
// Define the type of the graph
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties> Graph;
int main() {
// Create a graph object
Graph g;
// Add vertices
auto v0 = boost::add_vertex({1}, g),
v1 = boost::add_vertex({2}, g),
v2 = boost::add_vertex({3}, g);
// Add edges
boost::add_edge(v0, v1, EdgeProperties{1}, g);
boost::add_edge(v1, v2, EdgeProperties{2}, g);
boost::print_graph(g, boost::get(&VertexProperties::p1, g));
// set up a weight map:
auto weights = boost::get(&EdgeProperties::p1, g);
// you can pass itprint_graph`enter code here` to dijkstra using direct or named params. Let's do the simplest
boost::dijkstra_shortest_paths(g, v0, boost::no_named_parameters() .weight_map(weights));
}
您会注意到我也简化了顶点/边属性的初始化。如果您想了解图形的“外观”(不使用 Graphviz),print_graph 实用程序非常有用。
Coliru 上的输出是:
1 <--> 2
2 <--> 1 3
3 <--> 2
关于c++ - 具有捆绑属性的 BGL Dijkstra 最短路径,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/31145082/