問題タブ [longest-path]

このツリーでは:

ルートから始まる最長のパスはa-d-f-g

これが私の試みです：

main()関数内のツリーは、私が示した例ではありません。このツリーの場合、期待される結果は になりますa-c-f。このツリーを以下に示します。

今、私は得る

None基本ケースがあるため、そこにどのように表示されるかわかりません。

ありがとう！

標準入力からの入力で DAG の最長パスを見つけるプログラムを作成しています。最終的にコンパイルできました。配列リストが原因で未チェックまたは安全でない操作を使用しているとのことですが、インデックスを取得しています。境界エラーのエラーであり、すべてのループを変更しようとしたように感じます。何かが欠けているに違いありません。ヒントをお寄せいただきありがとうございます。これが私のコードです：

現在のコードでEDIT 1 これはエラーです：

最長/最短パスは、「頂点をトポロジー順に処理し、各頂点のパス長を、その入力エッジのいずれかを介して取得された最小または最大長になるように計算する」ことによって線形時間で見つけることができることを知っています。より簡潔に言えば、トポロジー的に分類してクリティカル パスを見つけます。

私の問題は、有効なパス内のエッジの最大数という別の制限を追加する必要があることです。ノードの「着信エッジのいずれかを介して取得される最大長」にはより多くのエッジが含まれる可能性があるため、これは問題を複雑にします。

これを解決する正しい方法は何でしょうか? それでも線形時間で解決できますか?

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

以下のように作成された簡単なグラフがあります

したがって、2つの可能なパスがあります

したがって、最長のパスは前者になります

最長パスを簡単に収集する方法はありA->B->D->Fますか?

与えられた: 任意の数のサイクルを含むことができる重み付けされていない有向グラフ (G=(E,V))。

目標: すべての頂点について、V 内のいくつかのターゲット頂点 X への最長の単純なパスが必要です

アルゴリズムのアイデア:

これはすべての場合に正しいですか？(すべての頂点からターゲットに到達できると仮定)

私のグラフのエッジの数は非常に少ないです。|E|とします。<= 3*|V| 保持します。平均時間の複雑さを計算するにはどうすればよいですか?

ありがとう！