graph - 各ノードが最大で 2 つの入力エッジと 2 つの出力エッジを持つ、グラフ内の最長パスを見つける

Question

タイトルが示すように、各ノードが最大で 2 つの入力エッジと 2 つの出力エッジを持つ有向グラフで最長パスを見つける必要があります。その事実が何かに役立つかどうかはわかりません。グラフには最大で 10000 個のノードがあります。そして、ノード 0 からノード 'Exit' までの最長パス (10001) を見つける必要があります。

ダイクストラをコーディングしようとしましたが、うまくいきませんでした。

前もって感謝します。

Answer 1

グラフを前処理し、ルールに違反するノードに接続されているエッジのエッジの重みを非常に高い値に設定してから、最長パスを返すダイクストラの修正バージョンを使用できます。