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）分组来测出延迟，接收者只对它加上时间标记后就尽快送回。