最優化的方式來解決多源多匯流網絡

Question

爲了簡單起見，假設我們有以下問題：

我們正在編寫自駕駛汽車的GPS在城市。我們假設運行我們軟件的汽車是道路上唯一的汽車。

城市的佈局被表示爲流動網絡，但流動網絡有多個起點/終點，因此有多個源/匯不一定彼此靠近。

是否有解決此問題的有效方法？

Answer 1

解決多源/多宿問題的標準方法是添加合成單源和合成單宿。一旦您將合成源連接到所有具有與源的容量相等的容量的實際源，並且還可以使用等於接收器容量的管道將合成源連接到所有實際接收器，則可以使用您的首選算法來解決單源/單水槽流量網絡。

Answer 2

是的，您可以創建一個虛擬來源，讓您的所有其他來源連接到一個虛擬來源，同樣，也可以爲所有要連接的實際接收器創建一個虛擬來源。

但是，您將什麼流程分配給從虛擬源到真實源的邊？從虛擬源到真實源（稱爲A）的邊緣應具有等於從A引出的所有邊的總和的流。同樣，從真實水槽（B）到虛擬水槽的邊緣的流動應該與進入B的所有邊的總和相同。

您可以在這些lecture slides中瞭解關於網絡流量的更多信息。