1樓：yukiyama
證明：Edmonds-Karp演算法時間複雜度為
閱讀如下詳細證明的前提是你已經完全掌握了EK演算法的步驟。證明開始（參考了網上找到的 證明1、證明2）。
a) EK演算法中一次BFS尋找增廣路的時間複雜度為 。
每次BFS增廣，在增廣路上的未飽和邊會多出一條反向邊，故增廣操作導致的邊數增長不會使總邊數超過原來的2倍，即演算法的任意時刻總邊數 。一次BFS的時間複雜為 ，即 。詳細可參考利用佇列的無權最短路徑複雜度分析。
b) BFS尋找增廣路的次數的時間複雜度為 。
b-1) 首先證明EK演算法通過BFS尋找的增廣路長度非遞減。
b-1-1) 假設某一次 的增廣後，使得某些頂點到源點 的最短路徑距離相比增廣前變小了，且這其中距離源點 距離最近者為 。則根據該假設有
b-1-2) 令 為中 的前乙個頂點，則有
如b-1-1)所述， 是我們有意選擇的在 中最短距離相比在 中變小的且距離 最近的頂點， 比 更靠近 ，但在中相比在中距離 的最短路徑未變小，即有
b-1-3) 假設，已知 到 的最短路徑距離為 ，則有
④結合①、②、③有
即④是由b-3)的假設得到的，與由①、②、③得到的 ⑤矛盾，故在b-1)假設成立的前提下，b-3)的假設 不成立，即 。
b-1-4) 由上述知 ，但如b-2)所述， ，故在 上的增廣經過了 ，且此邊飽和，導致在 中產生了反向邊 。於是可知在中有
⑥與⑤矛盾，於是最初b-1)的假設不成立，即不存在這樣的頂點 ，也即增廣操作使得源點到任意一點 的長度非遞減，故EK演算法尋找的增廣路( )長度非遞減。
b-2) 利用b-1)結論證明BFS尋找增廣路的次數小於 次。
b-2-1) 定義增廣路中的飽和邊為關鍵邊。某次增廣中的 為關鍵邊，增廣後 ， 。之後 要再次出現的前提是 為關鍵邊。
在 中 第一次成為關鍵邊，有
⑦b-2-2) 若 第二次成為關鍵邊，可知在此前的中 在成為關鍵邊，在的的這次增廣中有
b-2-3) 由b-1)的結論， 到任意頂點的最短路徑非遞減，有 ) ，結合⑦和⑧，有即⑨
也就是說， 第二次成為關鍵邊時 到 的最短距離至少比前一次成為關鍵邊時大2。而 到任意頂點的距離最多不超過 ，故 可以成為關鍵邊的次數最多為 。每次增廣至少有一條邊成為關鍵邊，根據b-1)中的說明，EK演算法過程中邊數 ，故考慮所有邊的總的增廣次數不會超過 ，即增廣次數複雜度為 。
綜上，EK演算法複雜度為 。
證明過程中BFS增廣使得增廣路非遞減的結論是關鍵，網上有的文章聲稱BFS尋找增廣路的操作使得增廣路遞增，這是不對的。根據b-1)的證明，只能得到非遞減的結果，但這一結論在b-2)中足以證明任意邊第二次成為關鍵邊時其最短路徑長至少增加2，由此得到BFS次數的上界。
2樓：minz
這個演算法導論最大流章節有證明，是先證明了如果一條邊被再次選為關鍵邊（應該就是你說的Engpasskante）那麼它連線的兩個點在殘存網路中到源點的最小距離（指所有所有邊都非零的路徑邊數的最小值）其中有乙個會至少比上次被選為關鍵邊的時候增加2，而最小距離是有上界|V-1|的，於是就推出了每條邊被選為關鍵邊的次數大於等於|V-1|/2+1（1是最初選的那一次），乘總邊數，再乘一次廣搜的複雜度得到最後的O(VE2）
ECC演算法與RSA演算法的優劣？
大家都說ECC對資源的消耗相較RSA更少，但是，TLS通訊中，不管是ECC還是RSA都是只在握手 交換會話秘鑰 session key 的過程中會用到。一旦這大概300ms的握手流程結束，後面就都是高效率的對稱加密，沒有ECC RSA啥事兒了。從我個人認為，ECC節省資源是個偽命題。節選自維基百科 ...
Sedgewick的演算法4中的KMP演算法有不少細節我看不懂，請大家幫我下？
Ben Shi 書中這個地方確實講解的有點不清楚 1.匹配的情況下狀態值是j 1，這個很容易理解，那麼需要搞清楚的就是不匹配的情況怎麼辦。2.不匹配只能從第二個字元 pat.charAt 1 開始重新進行匹配嘗試，因為當前就是從第乙個字元開始匹配失敗的，所以作者說 忽略首字母是因為模式需要右移一位 ...
A演算法和A 演算法的區別是什麼
若羽 A 演算法是一種可容納最優的啟發式搜尋演算法 其中 是最接近目標的真實代價，是實際A 演算法擬合的函式。伯克利的CS188課舉過這樣乙個例子 A是最優目標 區域性的 B是次優目標。B在邊緣，A的一些祖先節點n也在邊緣，代價函式f n 小於f A A 搜尋必須考慮forward cost和bac...