有約束的有向無環加權圖的遍歷

Question

我有一個有向無環加權圖，我想遍歷。

一個有效的解決途徑的約束條件是：

1. 所有邊的權重之和的路線走過必須是最高可能在圖中，以考慮第二個約束。
2. 在所選擇的路線（包括開始和結束頂點）中必須訪問完全N個頂點。

通常情況下，圖形將具有大量的頂點和邊，所以嘗試所有可能性不是一種選擇，並且需要相當高效的算法。

尋找一些指針或適合這個問題的算法。我知道使用Dijkstra算法很容易實現第一個條件，但我不確定如何合併第二個條件，甚至不知道從哪裏開始尋找。

請讓我知道是否需要任何額外的信息。

Answer 1

我不知道，如果你有興趣任何長度圖中的兩個特定頂點之間只是路徑N的路徑;我懷疑後者，但你沒有在你的問題中提到這種限制。

如果是前者，該解決方案應該是一個微不足道的Dijkstra樣算法您在其中所有的潛在路徑值始於邊的權重和邊緣得到由已建成adjecent路徑調整。在每次迭代中，採用具有最佳潛在路徑值的節點並將其添加到前瞻路徑。當你得到一條長度爲N的路徑時（或者在兩側切斷的路徑）停止。還有一些其他技術細節。 WRT。創造漫長的道路，但我不會詳細說明，因爲我懷疑這不是你感興趣的。:-)

如果你有固定的源和接收器，我認爲沒有深度的魔法 - 只是運行一個基本的Dijkstra，其中一個路徑將與添加到隊列中的每個頂點相關聯，但不會將具有> = N的路徑長度的頂點插入到隊列中，並且除非其路徑長度爲N，否則不要將接收器插入隊列中。