如何使用OGDF库在无圈有向图中找到最长路径？

Question

我是OGDF库的新手，需要在非循环有向图中找到最长路径(我想使用OGDF内置函数)。我知道，使用具有负权重的最短路径算法可以找到最长路径，但也找不到合适的函数。OGDF有没有特定的功能来做到这一点？如果是，我如何使用它？

Answer 1

在OGDF中，您可以使用ShortestPathWithBFM找到节点s和其他节点之间的最短路径。应使用EdgeArray<int>将边的长度(权重)传递给函数。下面是来自源代码的类定义：

namespace ogdf {

class OGDF_EXPORT ShortestPathWithBFM : public ShortestPathModule
{
public:
 ShortestPathWithBFM() { }

 // computes shortest paths
 // Precond.:
 //
 // returns false iff the graph contains a negative cycle
 bool call(
 const Graph          &G,      // directed graph
 const node           s,       // source node
 const EdgeArray<int> &length, // length of an edge
 NodeArray<int>       &d,      // contains shortest path distances after call
 NodeArray<edge>      &pi
 );


};


} // end namespace ogdf

如果您传递的长度为负数，该算法将计算最长路径。如需更多信息，请访问：http://www.ogdf.net/doc-ogdf/classogdf_1_1_shortest_path_with_b_f_m.html