如何使用OGDF库在无环有向图中找到最长路径？
我是OGDF库的新手，需要在无环有向图中找到最长的路径（我想使用函数中内置的OGDF）。我知道，用负权值的最短路径算法可以找到最长的路径，但也找不到合适的函数。OGDF是否有特定的功能来做到这一点？如果是，我如何使用它？
共有1个答案
在OGDF中，可以使用ShortestPathWithBFM查找节点S和其他节点之间的最短路径。应该使用edgearray
将边的长度（权重）传递给函数。以下是源代码中的类定义：
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
-
我需要为一组有向无环图找到从节点 0 开始的最长路径。我正在使用维基百科中的最长路径问题算法。我已经让算法适用于大多数图形，但对于其他图形，它没有给出正确的结果。算法为： 图形实现使用邻接列表来存储图形。如果我传递一个图，例如： 我得到的答案5，这是正确的。但是，如果我通过图表： 然后我得到2，而正确答案应该是3。 我使用的TopSort2算法是： DFS 算法包括：
-
我想在有向（无环）图中找到最长的路径。假设我知道起始节点-汇。路径应该从这一点开始。我在想我可以将边的权重设置为-1。有很多方法可以找到所有最短的路径，但你必须通过终点。有没有可能得到最短的路径（无论最终节点如何）？ 假设我想为节点 nr 1（汇）找到最长路径。所以这个算法给了我1-2-3-4-5-6。
-
我有一个一般性的问题，关于如何在边没有权的无向图中找到最短路径和最长路径。 我们需要使用DFS算法来寻找图中的最长路径，而我们需要使用BFS算法来寻找图中的最短路径，这是一个正确的结论吗？
-
我们得到了表格的邻接列表 意味着从U到V有一个成本C的优势。 给定的邻接列表适用于具有N个节点的单连通树，因此包含N-1条边。 给出了一组节点。 现在的问题是，在F中的节点中找到最长路径的最佳方法是什么？可以用O（N）来做吗？ 来自F中每个节点的DFS是唯一的选项吗？
-
我试图将这个问题概念化，然后为它编写Java代码。我知道这里有一些讨论，但我没有看到很多回答者，所以我想通过写下我的想法来重申这个问题，我希望从你们那里得到一些反馈。谢谢 我的想法：对于每个叶节点，找到从根节点到它的最长路径。对于所有路径，找到最大路径长度 然而，这不就是蛮力吗，对此还有更优雅的解决方案吗？ 我听说过使用Djikstra的负权重算法，但在某些地方它说这只适用于特定情况？我也看到了关
-
我需要找到图中最长的路径基于边权值。对于图像上的图，它应该是4,5,3,2,1（顺序无关紧要），最好的算法是什么？如果您知道，在您的图中，每个节点都有一个对图中任何其他节点的引用（边）。算法应该改变吗？