圖搜索特定長度路徑

Question

我有一個有向加權圖（帶週期），其中每個權重代表一段時間。 我想提出一個算法，它會給出在給定時間內訪問的最大節點數量（當然，訪問每個節點不會超過一次）。 有一個根節點可以從任何節點開始，路徑可以結束。

任何想法或指針？

（你問之前，這是基於作業的問題，我曾經有過，這種特殊的問題不是功課。）

Answer 1

我幾乎可以肯定，將是NP難的，所以任何圖形枚舉可能工作。例如，深度優先搜索。簡單的事情是添加一個標記，這樣你就不會遍歷一個路徑;列舉所有路徑，對權重進行求和，並追蹤最大值。