fordfulkerson演算法

1. 網路最大流問題——Ford-Fulkerson演算法

網路最大流問題的核心在於尋找一張有向圖（D=（V，A），其中A為弧集，V為點集）中從源點Vs到匯點Vt的最大流量。 Ford-Fulkerson演算法便是解決這個問題的關鍵工具。

首先，理解基本概念。在有向圖中，流f是一個滿足特定條件的函數，即對於弧（vi, vj）的容量c ij，0≤f ij≤c ij，並且在每個中間點處流出量等於流入量。流的可行性要求找到所有連通路徑，其中的每條路徑弧都是非飽和（即流量未達到最大）且前後弧的流量不為零（即增廣路徑）。

演算法的核心思想是從零流或已知可行流開始，通過標號過程（給每個點分配可能的增廣路徑信息）和調整過程（沿增廣路徑增加流量）來逐步增加流量。標號過程從Vs開始，對所有可達點進行標記，直到Vt或無增廣路徑為止。增流過程則是根據標號調整弧的流量，如果找到增廣路徑，就重復此過程，直到無法再增加為止。

福特-富克森演算法就是這樣通過反復尋找並利用增廣路徑，不斷更新流量，最終確定網路的最大流。這個過程的關鍵在於殘存網路的利用，即未被利用的流，它幫助演算法找到流量的增量路徑，直至達到網路的最大流量限制。

2. 距離向量路由演算法

距離向量路由演算法(Bellman-Ford Routing Algorithm)，也叫做最大流量演演算法(Ford-Fulkerson Algorithm)， 相應的圖片
其被距離向量協議作為一個演算法，如RIP, BGP, ISO IDRP, NOVELL IPX。使用這個演算法的路由器必須掌握這個距離表(它是一個一維排列-「一個向量」)，它告訴在網路中每個節點的最遠和最近距離。在距離表中的這個信息是根據臨近接點信息的改變而時時更新的。表中數據的量和在網路中的所有的接點(除了它自己本身)是等同的。這個表中的列代表直接和它相連的鄰居，行代表在網路中的所有目的地。每個數據包括傳送數據包到每個在網上的目的地的路徑和距離/或時間在那個路徑上來傳輸(我們叫這個為「成本」)。這個在那個演算法中的度量公式是跳躍的次數， 等待時間，流出數據包的數量，等等。 在距離向量路由演算法中，相鄰路由器之間周期性地相互交換各自的路由表備份。當網路拓撲結構發生變化時，路由器之間也將及時地相互通知有關變更信息。

路由表的建立和更新
如上圖，有三個路由器，A，B和C。路由器A的兩個網路介面E0和S0 分別連接在 10.1.0.0和10.2.0.0網段上；路由器B的兩個網路介面S0和S1 分別連接在 10.2.0.0和10.3.0.0網段上；路由器C的兩個網路介面S0和E0 分別連接在 10.3.0.0和10.4.0.0網段上； 如上圖中各路由表的前兩行所示，通過路由表的網路介面到與之直接相連的網 絡的網路連接，其向量距離設置為0。這即是最初的路由表。 當路由器B和A以及B和C之間相互交換路由信息後，它們會更新各自的路由表。 例如，路由器B通過網路埠S1收到路由器C的路由信息（10.3.0.0,S0,0）和(10.4.0.0,E0,0) 靜態路由的具體配置
後，在自己的路由表中增加一條(10.4.0.0,S1,1)路由信息。該信息表示：通過路由器B的網路接 口S1可以訪問到10.4.0.0網段，其向量距離為1,該向量距離是在路由器C的基礎上加1獲得的。 同樣道理，路由器B還會產生一條(10.1.0.0,S0,1)路由，這條路由是通過網路埠S0從路由器A 獲得的。如此反復，直到最終收斂，形成圖中所示的路由表。 概括地說，距離向量演算法要求每一個路由器把它的整個路由表發送給與它直接連接的其它路由 器。路由表中的每一條記錄都包括目標邏輯地址、相應的網路介面和該條路由的向量距離。當一個路 由器從它的相鄰處收到更新信息時，它會將更新信息與本身的路由表相比較。如果該路由器比較出一條 新路由或是找到一條比當前路由更好的路由時，它會對路由表進行更新：將從該路由器到鄰居之間的 向量距離與更新信息中的向量距離相加作為新路由的向量距離。
參與運算信息
目的地址：在演算法的IP實現中，這指的是主機或的IP 地址。 下一跳地址：到信宿的路由中的第一個路由器。 介面：用於到下一跳物理。 metric值：一個數，指明本路由器到信宿的開銷。 定時器：路由項最後一次被修改的時間。 路由標記：區分路由為內部路由協議的路由還是外部路由協議的路由的標記。
運算
路由器間交換的最重要的信息是修改報文，參加路由維護計劃的路由器發送當前存在於實體的描述路由庫的路由修改報文。僅通過相鄰路由器間交換路由信息是可以維護整個系統的最佳路由的，這在接下來的討論中會逐步得到證明。 距離向量演算法總是基於一個這樣的事實：路由庫中的路由已是目前通過報文交換而得到的最佳路由。同時，報文交換僅限於相鄰的實體間，也就是說，實體共享同一個。當然，要定義路由是最佳的，就必須有衡量的辦法，這就用到前面所說的「metric」。RIP簡單的中，通常用可行路由所經的路由器數簡單地計算metric值。在復雜的中，metric一般代表該路由傳輸報的延遲或其它發送開銷。 令D代表從實體i到實體j的最佳路由的metric值，d（i，j）代表從i直接到j的開銷，因為開銷是可加的，演算法中最佳路由如此獲取表示： D（i，i）=0， 對所有的i D（i，j）=MIN[d（i，j）+D（k，j）， 當i不等於k時 實體i從相鄰路由器k收到k到j的開銷的估計D，i將D（i，j）加上i到k的開銷估計d（i，j），i比較從所有相鄰路由器得到的數值，取得最小數，就得到了它到j的最佳路由。

3. Ford-Fulkerson演算法正確性證明

圖論中有一類重要的問題就是流量問題。求一個流網路的最大流量。那麼可以用的方法有很多，比較經典的是FF(Ford-Fulkerson)演算法。本文主要描述FF演算法正確性的證明。涉及到的知識點：

其中我們用最大流-最小割定理來證明FF演算法的正確性

一個流網路的定義如下：

流網路 是一個有向圖。具有如下屬性：

流網路中有兩個重要的頂點 ，其中s叫做源點（source），t叫做匯點（sink）。流網路中的流是從源地點到匯點。流網路中的所有流都從源點出發，然後最終都流入匯點。

如圖就是一個流網路的示意圖：

網路G的流是一個如下的一個函數：

流具有如下性質：

一個流的值用 表示

表示從 流出的所有值減去流入 的所有值

我們定義一個流網路的割（cut）為：

其中

就是將一個圖分割為兩個不相交的集合。s在其中一個集合中，t在另外一個集合中，並且兩個集合中的點是不相連的

我們引入一些網路流割的屬性：

為了證明FF的正確性，我們需要引入一個引理來輔助證明過程

設 為流網路中的一個流，橫跨任何切割的凈流量都相同，都為 ，即流的值。即證明

證明有兩種方式，一種是嚴格的數學證明，另外一種是直觀上的感受，如果對於數學證明沒有興趣的話，那麼可以直接去看直觀上的證明。

對於 流量守恆 特性，我們有： ，

根據流的值的定義：

，將上面的式子針對每一個 相加得到

我們可以看到，這個等式前面括弧的一部分就是 ，後面的一部分根據 流量守恆 知道為0

因此

證畢。

根據流的定義，我們知道一個流網路 的流 的值是所有從 流出的流的和，減去所有進入 的流。那麼從 出去的流，最後都會進入到 中。而我們任意的一個切割，都將這個網路分成了兩個不相連的部分， 位於一部分 位於一部分。如果流想要從 到 的話，那麼必須經過這個切割。而流網路是沒有損耗的，因此經過這個切割的流的值，一定等於從 中流出的值和流入值的差，也就是整個網路的流的值。即 證畢。

有了引理1，我們就可以有推論1：網路的流小於或等於網路任意切割 的切割容量，即

證明推論1:

根據引理1，我們知道。網路的流等於任意橫跨切割的流，而再根據 容量限制 我們知道橫跨任意切割的流小於等於切割的容量。傳遞過來，我們就有，網路的流小魚等於任意切割的容量，即

證畢。

有了推論1，我們就可以很明顯的得出。一個網路的最大流的值等於一個最小切割的容量。即最大流-最小切割定理。

設 為流網路 中的一個流，該流網路的源點為 ，匯點為 ，則下面的條件是等價的：

(1) 是 的一個最大流
(2) 殘存網路 不包括任何增廣路徑
(3) ，其中 是流網路 的某個切割

我們可以看到，FF演算法在可以終止的前提下，終止的條件是（2），我們假設在（2）的前提下有（1），也就是 我們就是需要證明

我們使用反證法來證明。如果一個 是最大流，但是 中存在增廣路徑，那麼根據FF演算法就可以增加網路的流的大小，那麼這個流就不是最大流了。與我們最初的假設矛盾，因此 是正確的

中不存在增廣網路，那麼我們就可以將 切割為 定義 ，那麼顯然有 。 我們對於 會有下面兩個推論：

有上面的兩個推論，我們結合跨切割的流的定義有：

根據引理1，我們有

因此 正確

根據推論1，我們知道 ，而 中的等於前提，即 即表明了這是一個最大流。因此 是正確的

經過上面的證明我們可以看到， 是一個獨立的條件，那麼就會有 這樣的證明鏈條，也就有 也就是我們要證明的結論，即FF演算法的正確性--在沒有殘差網路的情況下得到的流一定是最大流。事實上 互為充要條件。

證畢。

4. 距離矢量協議的路由演算法

距離矢量路由演算法是動態路由演算法。它是這樣工作的：每個路由器維護一張矢量表，表中列出了當前已知的到 每個目標的最佳距離，以及所使用的線路。通過在鄰居之間相互交換信息，路由器不斷地更新它們內部的表。
距離矢量路由演算法最常見的是Ford－Fulkerson演算法。該演算法的核心思想是使用標號的方法不斷尋找一個圖上的 可增廣路徑團迅並且進行調整，直到找不到可增廣路徑為止。距離矢量路由演算法號召每個路由器在每次更新時發送它 的整個路由表，但僅僅給它的鄰居。距離矢量路由演算法傾向拿或肢於路由循環，但比鏈路狀態路由演算法計算更簡單。
演算法描述如下：
給定帶杈有向圖G和源點s，求從s到G中任意頂點v的最短路徑，該演算法通過在一個路由中重申跳數的個數九來尋 找一個最短路徑生成樹。
在距離矢量路由選擇演算法中，每個路由器維持有一張子網中每一個以其他路由器為索引的路由選擇表，表中的 每一個項目都對應於子網中的每個路由器。此表項包括兩個消世部分，即希望使用的到目的地的輸出線路和估計到達 目的地所需時間或距離。用度量標准可為站點，估計的時間延遲（ms），該路出排隊的分組估計總數或類似的值。
假定路由器知道它到每個相鄰路由器的「距離」。如果度量標准為站點，其距離就為一個站點；如果度量標準是隊列長度，則路由器會簡單地檢查每個隊列；如果度量標準是延遲，路由器可以直接發送一個特別「響應」（ECHO）分組來測出延遲，接收者只對它加上時間標記後就盡快送回。