1

私はOGDFライブラリを初めて使用し、非巡回有向グラフで最長のパスを見つける必要があります(OGDF組み込み関数を使用したい)。エッジに負の重みを持つ最短経路アルゴリズムを使用して最長経路を見つけることは可能ですが、適切な関数を見つけることもできませんでした。OGDFにはそれを行うための特定の機能がありますか?はいの場合、どうすれば使用できますか?

4

1 に答える 1

0

sOGDFでは、を使用してノードと他のノード間の最短経路を見つけることができます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を参照してください。

于 2012-08-11T20:44:24.130 に答える