Как найти самый длинный путь в ациклическом ориентированном графе с помощью библиотеки 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