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

Question

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

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

我有两个问题：

如何在 Boost 中将 My Graph 馈入 Dijkstra 算法，我的意思是如何从 My Graph 中提取属性（即数千个顶点和边）以馈入 Dijkstra 参数。
示例中算法的输出是图中一个节点与其余节点之间的最短路径，所以我如何才能只获得我的源节点和目标节点之间的最短路径？我应该过滤输出结果以构建我的最短路径向量吗？

//===========================================================================
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

Answer 1

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

你不能只向 dijkstra 算法询问一条路径，因为路径是逐渐形成的，但是，你可以为每个节点保存一个父节点，它说明哪个节点是该节点的前一个节点起始节点和结束节点。之后就可以从目标节点开始，获取它的父节点，直到到达起始节点。

Answer 2

首先，如果没有对每个节点的接近程度进行成本估算，您就无法使用 Dijkstra。

也就是说，这个问题足够小，您可以简单地从一开始就进行广度优先搜索以找到到达目标的最佳路径。

如果你想让它更有效率，你可以同时从源和目标进行搜索，找到它们相遇的地方。保证最优有点棘手，但这使得平均搜索速度更快。

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

How to get shortest path between 2 nodes only, given adjacency list directed graph?

c++

algorithm

boost

dijkstra

boost-graph

我有两个问题：