ford-fulkerson

1熱度

1回答

我正在閱讀由Robert Sedgewick編寫的書算法中的Ford-Fulkerson maxflow算法。這裏作者提到如下 Ë邊緣在最短增強路徑實施福特 - 富爾克森maxflow算法的所需的流動網絡採用V頂點增廣路徑和的數量最多爲EV/2 。證明草圖：每個增強路徑具有從剩餘網絡，因爲它對應要麼變得滿額或被排空後向邊緣前邊緣刪除的臨界邊緣的邊緣。每當邊緣是臨界邊緣時，穿過它的增大路

1熱度

2回答

查找流網絡的最小割

我試圖找到下面網絡的最小割我使用下面的算法：潤福特Fulkerson算法，並考慮最終殘差圖。找到殘差圖中可以從源訪問的一組頂點。從可到達頂點到不可到達頂點的所有邊都是最小切割邊。打印所有這些邊緣。在第一步驟中，我的算法找到3條路徑： - s->b->h->t **value: 1** - s->d->e->t **value: 1** - s->c->h->i->m->d->g->t

0熱度

1回答

Ford-Fulkerson方法中的修改

我想在流網絡G中的所有最小切割中找到包含最小邊數的積分容量。我們怎樣才能修改G的能力，以創建一個新的流網絡G「中的任何最低切G」是G. 來源與邊緣的最小數量的削減最低 - Cormen

0熱度

1回答

實現Ford-Fulkerson的函數中的分段錯誤

我正在處理一個類的任務，並且遇到了一個我一直無法解決的問題。我正在使用BFS實現Ford-Fulkerson算法來查找最大流量。但在試圖將我的剩餘容量矩陣設置爲給定容量時，我遇到了分段錯誤。在我們收到的測試代碼中，我可以看到原始容量矩陣是通過地址值傳遞的，但是我有一種感覺，在我的代碼中，我沒有像我認爲的那樣與它交互？這導致我相信我可能會在其他地方發生同樣的問題。我曾用gdb，看到我打分割故障在這條

0熱度

1回答

選擇ford fulkerson算法中的增廣路徑

如果在給定流網絡的剩餘網絡中存在很多增廣路徑，那麼我應該在首先找到哪條路徑來查找瓶頸容量？

1熱度

1回答

查找任何網絡的最大流量由給定的算法

你能幫助我有以下問題？：假設我們有一個算法來解決流量網絡中每個節點的出度是最大流量的問題最多2. 我需要展示如何使用這種算法來解決任何網絡中的最大流量問題。如果這是一個重複，那麼請將我重定向到相關答案。謝謝所有

0熱度

1回答

使用Ford Fulkerson從流量中去除邊緣後有效計算最大流量

假設已經使用Ford-Fulkerson計算出了G的最大流量，但現在已從E中移除了一條邊線，如何可以有效更新最大流量。

1熱度

1回答

什麼是節點不相交路徑？

我需要解釋一下哪些節點不相交的路徑？以及如何確定有向圖中兩個節點Source（s）和Sink（t）之間的節點不相交路徑的最大數量。任何人都可以用圖形來解釋。

1熱度

1回答

最有效的方式改變一個邊緣的能力後重新計算在圖形流

什麼是最有效的方式來重新計算在圖形最大流量時：我們通過一個增加一個邊流我們在一條邊上減少流量在第一種情況下，是否足以運行Ford-Fulkerson算法的一次迭代？在第二種情況下，只有當邊緣是最大流量邊緣集合的一部分時，我們才需要重新計算最大流量。運行Ford-Fulkerson的一次迭代也足夠了嗎？

0熱度

1回答

繼續福特 - 福爾克森

我想學習福特 - 福爾克森的方法。我已經爲練習做了一個例子，在某些時候我不能繼續增加流量，但我知道流量可能會更高。首先，我已經加了路徑s -> 1 -> 2 -> t。現在我找不到增加流量的路徑。我知道如果我先通過a -> 1 -> 5 -> 6 -> t，那麼我可以遞增路徑s -> 3 -> 4 -> 2 -> t，但是如果我必須實施它，我不知道該怎麼做。我在做什麼錯？