演算法 日更 第三十五期 FF演算法優化 EK演算法

2022-11-24 17:31:56 字數 2164 閱讀 2498

▎寫在前面

ff演算法傳送門

之前我們已經學過了ff演算法(全稱ford-fulkerson演算法)來找最大流,但是這種演算法仍有諸多不對的地方。

其實這種演算法存在著嚴重的效率的問題,請看下面的圖:

以這個圖為例,我們使用的搜尋是無規則選邊的,可能第一次會選這樣的一條邊。

那麼我們繼續增廣。

第二次我們可能會選這樣一條邊:

發現什麼了沒有?邊一直在減1,那麼如果這樣迴圈下去,的確有嚴重的效率問題。

但是我們明明可以通過s -> 1 -> t或s -> 2 -> t就可以到達,且不存在效率問題,但是人眼能分辨出來,程式可不行,那麼我們就應該請出ek演算法了。

▎edmonds-karp演算法

☞『定義』

☞『本質』

其實說白了就是優先尋找最短路的ff演算法。

▎演算法高效性證明

☞『引理1』

引理:令fi表示增廣i次後得到的容許流,λk(u,v)表示fk中u到v的一條最短路長度,那麼就有:

λk(s,v)≤λk+1(s,v),λk(v,t)≤λk+1(v,t)

證明:

假設fk+1中有一條從s到t的最短路為s=u0,u1,…,up-1,up=v,其中邊記為e,ei表示(ui-1,ui)的長度,**一下是這樣的:

那麼這是k+1次增廣的結果,那麼我們繼續思考k次會是怎樣的。

對於每一條邊ei,都會有兩種情況:

①在fk中也是可以使用的(沒有用於此次增廣),那麼顯然有λk(s,ui)≤λk(s,ui-1)+1;那麼i與i-1有連邊,所以可能等於,因為s到ui的最短路可能是從其他點繞過來的,所以可能是小於的;

②在fk中是不可以使用的(用於了增廣),那麼很顯然λk(s,ui-1)=λk(s,ui)+1;這個不好講,放張圖自行體會吧。

綜上,就有λk(s,v)≤λk+1(s,v)了。

『引理2』

引理:設邊e在fk變為fk+1的增廣路上,e´在fl變為fl+1的增廣路上(kλl(s,t)≥λk(s,t)+2

證明:假設e=(u,v),那麼顯然:

λk(s,v)=λk(s,u)+1

λl(s,t)=λl(s,u)+1+λl(u,t)

再由引理1替換得:

λl(s,t)≥λk(s,t)+2

『演算法時間複雜度分析』

若邊e在fk1,fk2,fk3,…中成為瓶頸(就是變化為0了),那麼就必定存在fl1,fl2,fl3…,滿足k112

2就是說e在ki次增廣時變成逆向的,在li次增廣時變為正向的,這樣ki+1次可以繼續增廣。

顯然,s到t的最短路在1到n-1之間,其中n是總點數,每次改變e的方向,都會導致最短路長度加2(引理2)。

如果是第kj次增廣,那麼e變化的次數不可能超過2j-2次,就有:

2(2j-2)≤n-1-1(變化量小於上界減下界),把j單獨移到一邊去,就得到j≤(n+2)/4,由於一條邊還有反向弧,所以一條邊至多成為(n+2)/2次瓶頸,也就是說最多有m(n+2)/2條增廣路。

這樣,這個演算法的時間複雜度就與權值無關了。

演算法 日更 第四十五期 靜態二叉排序樹(建立)

前言 小編雖然已經會了二叉排序樹,但是卻不明白靜態二叉排序樹和二叉排序樹有什麼關係。結合平衡二叉排序樹 例如 紅黑樹 食用本篇部落格,效果更佳哦 傳送門 同時也內含二叉排序樹的相關知識 靜態二叉排序樹 引入 這個東西要從線段樹說起,別問我為什麼扯這麼遠。戳這裡快速上手線段樹。不得不說,線段樹是個好東...