时间戳

首页 > 解决方案 > 给定邻接列表有向图，如何仅获得 2 个节点之间的最短路径？

c++ - 给定邻接列表有向图，如何仅获得 2 个节点之间的最短路径？

问题描述

我有一个用以下代码表示的图表：

typedef adjacency_list < vecS, vecS, directedS, property < vertex_name_t, idType >, property < edge_weight_t, double > > graph_t;

我有两个问题：

  1. 如何将我的图输入到 Boost 中的 Dijkstra 算法中，我的意思是如何从我的图（即数千个顶点和边）中提取属性以输入 Dijkstra 参数。

  2. 示例中算法的输出是图中一个节点与其余节点之间的最短路径，那么我如何才能只获得源节点和目标节点之间的最短路径？我应该过滤输出结果以构建我的最短路径向量吗？ 

//===========================================================================
MyAlgorithm::MyAlgorithm(graph_t AnyGraph, Vertex VSource){// Parameters Constructor

  MyGraph = AnyGraph;
  vector<Vertex> p(num_vertices(AnyGraph));
  //  for(auto j = p.begin(); j != p.end(); ++j)
  //      cout <<"P["<< *j<<"] = "<<p[*j]<<endl; 
  vector<double> d(num_vertices(AnyGraph));
  //  for(auto j2 = d.begin(); j2 != d.end(); ++(j2))
  //      cout <<"d ["<< *(j2)<<"] = "<<d[*(j2)]<<endl; 
  //===========================================================================
  //Dijkstra_Algorithm
  //===========================================================================
  cout<<"Before\t"<<endl;
  dijkstra_shortest_paths(AnyGraph, VSource,
                          predecessor_map(boost::make_iterator_property_map(p.begin(), get(boost::vertex_index, AnyGraph))).
                          distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, AnyGraph))));
  cout<<"After\t"<<endl;
  //===========================================================================
}// End of Parameters Constructor

标签： c++algorithmboostdijkstraboost-graph

解决方案

我正在回答你的第二个问题：

您不能只针对一条路径询问 dijkstra 算法，因为路径是逐渐形成的，但是，您仍然可以为每个节点保存一个父节点，该父节点在开始节点和结束节点之间的路径中说明哪个节点是该节点的前一个节点节点。之后，您可以从目标节点开始，并获取其父节点，直到到达起始节点。

推荐阅读