graph - 如何使用 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