0

特定の頂点から始めて、その頂点に相対的な最長パスをどのように見つけますか? 私はずっとブラウズしてきましたが、DAG の考えられるすべてのケースで実際に機能するこの問題の解決策を見つけることができません。NetworkX のソース コードが推奨されますが、通常の python でも問題ありません。適切な実例を見つけることができない理由について本当に興味があります.NPタイプの問題であることは理解していますが、最も効率的な方法を知りたいです.

4

1 に答える 1

1

まず、このグラフが接続されているかどうかを確認します。その場合、最長パスはすべてのノードにわたるパスです。そうでない場合は、この頂点が接続されたコンポーネントに含まれていることを意味します。次にconnected_component_subgraphs、この頂点がある最大のコンポーネントを見つけるために使用します。その後、最長のパスは、この最大のコンポーネント内のすべてのノードにわたるパスです。

もちろん、これはパスにサイクルを許可しない場合にのみ機能します。

import networkx as nx 
G = nx.DiGraph()  
G.add_edges_from([(0,1),(0,4),(4,5),(4,6),(5,6),(6,1),(0,2),(2,3),(1,2)])  
for path in nx.all_simple_paths(G, source=0, target=3):  
    print(path)

結果：

[0, 1, 2, 3]
[0, 2, 3]
[0, 4, 5, 6, 1, 2, 3]
[0, 4, 6, 1, 2, 3]

3つ目はあなたの好みです。

于 2016-09-25T12:52:32.273 に答える