利用負循環尋找圖形上兩個節點之間的零/負重路徑

Question

我真的很努力在標題中描述這一點，但我會以更長的格式給出它。

我真的難住這個問題，我不是在尋找答案，只是一些幫助或一些特定的主題來閱讀。

我所擁有的是一個帶有不同權重的邊的有向圖，既有正面也有負面。我試圖做的是編寫一個算法，該算法提供兩個位於圖上的節點（並假設它們已連接）找到它們之間的路徑，導致路徑的總權重爲零或負值。路徑可以多次包含節點（希望允許路徑抵消包含邊的正面權重）。

我目前正在閱讀Russel和Norvig的人工智能，但我正在努力尋找一種方法來將文本中的邏輯應用於由於各種問題（算法不斷循環負循環）而導致的問題。我不完全瞭解如何利用Backtrack和AStar等方法來幫助我更好地理解我的問題，如果有人能指出我的正確方向，那將會是一個很好的幫助，在處理DFS和BFS以及與圖形有關的許多其他事情方面還不錯，但是必須在兩個節點之間找到一個具有重量限制的路徑，這真的讓我感到困惑。

感謝

下面我已經包含了樣品圖，我需要能夠找到目標所在的路徑的總重量不超過零從開始的路徑。

示例繪製 http://i144.photobucket.com/albums/r166/ZooropaTV/bu.jpg

剛剛意識到，很多檢索/閱讀中，我一直在做的一直是誤導，因爲我的目標不一定會按重量找到最短路徑，而是通過訪問節點的最低要求數量，我現在需要有另一個想想，但還是想任何建議

Answer 1

我覺得這是你想要的一切：弗洛伊德 - Warshall算法http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

ÿ你必須修改它以適應你的需要，但它會檢測負循環，從而使你找到一條零重量或更輕的路徑。