我正在尝试在BGL中使用Dijkstra最短路径算法来计算无权无向图上的简单ST路径。将来可能会关注边权重,但现在我只想将边遍历视为统一成本。
我还跟踪多个边缘和顶点属性,因此我所做的基于bundled properties example,该示例似乎是我要尝试的最接近的示例。
现在我正在尝试弄清楚如何使dijkstra工作,以便我可以进行我的ST搜索,但我卡在了为其设置正确参数上。
这是我目前拥有的代码的简化示例:
我在调用Dijkstra算法时,对正确的参数感到困惑。它们需要图形、起始顶点以及前任映射和距离映射。到目前为止,我看到的例子,比如this one,只设置了边权重而没有捆绑边属性,这简化了事情。
最终,我需要ST最短路径,因此需要从S到T恢复路径。从事情的外观来看,我们需要设置一个前任映射,然后我们可以使用它从特定的T回到S中提取路径?
我还应该注意,我所处的环境不允许使用C++11语言功能。:(
非常感谢您在这里提供的任何帮助!
我还跟踪多个边缘和顶点属性,因此我所做的基于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恢复路径。从事情的外观来看,我们需要设置一个前任映射,然后我们可以使用它从特定的T回到S中提取路径?
我还应该注意,我所处的环境不允许使用C++11语言功能。:(
非常感谢您在这里提供的任何帮助!