最長/最短パスは、「頂点をトポロジー順に処理し、各頂点のパス長を、その入力エッジのいずれかを介して取得された最小または最大長になるように計算する」ことによって線形時間で見つけることができることを知っています。より簡潔に言えば、トポロジー的に分類してクリティカル パスを見つけます。
私の問題は、有効なパス内のエッジの最大数という別の制限を追加する必要があることです。ノードの「着信エッジのいずれかを介して取得される最大長」にはより多くのエッジが含まれる可能性があるため、これは問題を複雑にします。
これを解決する正しい方法は何でしょうか? それでも線形時間で解決できますか?