設G =（V，E）是n> = 3個m邊的頂點的有向圖。頂點集合V包括三個特殊頂點a，v和b。如果存在，則通過v找到從a到b的簡單路徑。 （一個簡單的路徑是沒有重複頂點的路徑）
我相信這個問題應該可以用Max Flow算法解決，但我不知道如何。它讓我想起了一個Max Flow算法，該算法具有多個來源，其中邊緣具有容量1.任何人都知道如何將問題簡化爲最大流量算法？
如果我將頂點b設置爲接收器，我不能確定它將包含v。如果我將v設置爲接收器，當達到v時我該如何繼續？
下面應該工作：
找到所有最小路徑從a到v，那不包含頂點b。您可以通過（例如）圖形上的DFS獲取這些頂點，但不包含頂點b。我們說a-v -path p是最小的，如果沒有其他a-v -path p'只包含來自p的頂點。
每個最小a-v -path，試圖找到從v到b忽略頂點已經屬於a-v -path的路徑。如果你發現這樣的事情，你就完成了。
注：注意路徑的數量可能會增長指數，但正如我在我的評論中指出，至少在這個問題的通用版本似乎是還原到TSP，因而是可能很難。
這也是我能找到的唯一解決方案。不是我所希望的答案：/ – 2012-01-04 22:31:17
這相當於詢問圖是否包含與三個頂點的有向路徑同胚的子圖（模式是輸入圖中某些頂點的圖形，並且子圖是同胚於模式的該模式可以映射到子圖的簡單的，成對的頂點不相交路徑）。 Fortune, Hopcroft, and Wyllie已經證明，對於幾乎所有的固定模式，包括這個，指導子圖同胚都是NP難。所以這個問題是NP難的，除非P = NP，否則不能用流技術來解決。
儘管可以通過讓a和b成爲源代碼並使用接收器，但可以將無向版本降低到最大流量。
不會只是b的第二條路徑的來源嗎？ – Mikeb 2012-01-04 21:23:41
你可以嘗試谷歌的「最大流量下限」。如果你強制頂點v的最小流量爲1，那麼你基本上有一條通過v。 – phimuemue 2012-01-04 21:33:55
@Mikeb的路徑我不這麼認爲。從a-> v的流動可能是一條路徑，使我不可能從v-b流出一個流。 – 2012-01-04 21:43:34