Boost Graph 中的最长路径

Question

抱歉，如果这对你们中的一些人来说是一个非常基本的问题，但我是 C++ 新手（更不用说 Boost Graph Library）并且无法解决这个问题。到目前为止，我已经能够使用下面的代码制定/收集代码来创建图表。

现在我正在尝试找出找到该图中最长路径的代码。

有人可以帮忙看看代码是什么吗？在尝试查找路径时，我无法弄清楚是否/如何遍历每个节点和/或边缘？

我必须尝试返回最长路径中的所有节点和边。

任何帮助将不胜感激。

PS 有谁知道 C++ 是否有像 Javadoc 那样组织文档？

    #include <boost/graph/dag_shortest_paths.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <windows.h>
#include <iostream>



int main()
{
  using namespace boost;
  typedef adjacency_list<vecS, vecS, directedS, property<vertex_distance_t, double>, property<edge_weight_t, double> > graph_t;
  graph_t g(6);
  enum verts { stationA, stationB, stationC, stationD, stationE, stationF };
  char name[] = "rstuvx";


  add_edge(stationA, stationB, 5000.23, g);
  add_edge(stationA, stationC, 3001, g);
  add_edge(stationA, stationD, 2098.67, g);
  add_edge(stationA, stationE, 3298.84, g);
  add_edge(stationB, stationF, 2145, g);
  add_edge(stationC, stationF, 4290, g);
  add_edge(stationD, stationF, 2672.78, g);
  add_edge(stationE, stationF, 11143.876, g);
  add_edge(stationA, stationF, 1, g);




//Display all the vertices
  typedef property_map<graph_t, vertex_index_t>::type IndexMap;
  IndexMap index = get(vertex_index, g);
  std::cout << "vertices(g) = ";

  typedef graph_traits<graph_t>::vertex_iterator vertex_iter;
  std::pair<vertex_iter, vertex_iter> vp;
  for (vp = vertices(g); vp.first != vp.second; ++vp.first)
      std::cout << index[*vp.first] <<  " ";
  std::cout << std::endl;
  // ...

   // Display all the edges
    // ...
  std::cout << "edges(g) = " << std::endl;
    graph_traits<graph_t>::edge_iterator ei, ei_end;
    for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
  std::cout << "(" << index[source(*ei, g)] << "," << index[target(*ei, g)] << ") \n";
    std::cout << std::endl;
    // ...

Answer 1

我认为你应该检查你的 boost 发行版中的示例。在线：http ://www.boost.org/doc/libs/1_38_0/libs/graph/example/dijkstra-example.cpp

为了让它找到最长的路径，您需要简单地反转权重 (W)，可以使用常数 - W 或 1/W。如果常数为 0，则表示它是负数 (-W)。