c++ - Boost Graph Library:最短的周期，有资源限制

Question

问题

在具有任意弧长(行进时间，成本)的有向图中，找到最短(最快，最便宜)的循环(或没有重复顶点的闭合行走)。或者，找到通过给定顶点的最短周期。

寻求解决方案

r_c_shortest_paths的the Boost Graph Library解决了……最短路径的确切问题。 example清楚地演示了其用法。

尽管尝试了几种方法，但无法有效地将r_c_shortest_paths用于上述问题。

题

是否可以使用r_c_shortest_paths解决此问题？如果是这样，怎么办？

另一种BGL算法？

另一个C++图形库？

谢谢

Answer 1

如果您不想写点东西，例如从原点可完整遍历图(可能不那么糟糕或那么困难)，则此处阻力最小的路径(尤其是考虑到图的方向)可能会仅在原点的每个邻居上使用r_c_shortest_paths(就正确的方向而言)。假设一个实现将是这样的:

std::vector<Path<Nodes>> best_paths;
size_t first_step = -1;
for(auto&& [neighbor, weight] : boost::zip(origin.neighbors(), origin.weights())) {
    auto paths = r_c_shortest_paths(neighbor, origin);
    if(!paths.empty() && (best_paths.empty() || paths[0].cost + weight < best_paths[0].cost + first_step)) {
         best_paths = paths
         first_step = weight
    }
 }