如何使用OGDF库在非循环有向图中找到最长路径？

Question

我是OGDF库的新手，需要在非循环有向图中找到最长的路径（我想使用内置函数的OGDF）。 我知道，有可能找到最长的路径使用负边权重为最短路径算法，但也找不到适当的函数。 OGDF有具体的功能吗？ 如果是，我该如何使用它？

Answer 1

在OGDF中，您可以找到节点s和使用ShortestPathWithBFM的其他节点之间的最短路径。应使用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