算法分析与复杂性理论实验报告最大流问题.docxVIP

深 圳 大 学 实 验 报 告 课程名称：算法分析与复杂性理论 实验名称：实验五最短增益路径法求最大流问题 学院：计算机与软件学院专业：软件工程 报告人：文成学号： 2150230509班级：学术型 同组人：无 指导教师：杨烜 实验时间： 2015/11/23—— 2015/11/30 实验报告提交时间： 2015/11/28 教务处制 一． 实验目的与实验内容 实验目的： 1） 掌握最短增益路径法思想。 2） 学会最大流问题求解方法。 实验内容： 给定下面的通信网络，该网络中各节点之间的路径流量给定，使用最短增益路径法求解该网络的最大流量，并进行流量分配。 要求用加权矩阵输入该网络， 输出每次迭代过程中的最大流量及各路径分配的流量。 如果能利用图形界面输出动态求解过程 （在网络结构的图形显示中， 标注每一次求得的增益路径，并显示当前流量分配），可获加分。 算法思想提示： 利用二维数组 C[i,j] 和 F[i,j] 分别存放容量和流量。 构建队列类 Queue，该类具有取队首元素，加入队尾元素等方法。 具体算法过程参见教材 pp.271-272 二．实验步骤 最大流问题的问题描述： 如上图。 s 是源点， t 为汇点，每条边上数字的含义是边能够允许流过的最大流量。可以将边看成管道， 3 代表该管道每秒最多能通过 3 个单位的流量。最大流问题即是说，从 s 点到 t 点，最大允许流量是多少？ 最大流问题的算法思想： 最短增益路径法 ( 先标记先扫描算法 ) ： 用两个记号来标记一个新的顶点 第一个标记指出从源点到被标记顶点还能增加多少流量 第二个标记指出另一个顶点的名字，可加上 +或- 来表示顶点时通过前向边还是后向边访问到的 算法及其伪代码： Maxflow(G) 最短增量路径算法的实现 输入：网络 G，具有一个源点 1 和一个汇点 n，每条边（ i ，j ）的容量都是正整数 Uij 输出：最大流量 x 对网络中的每条边（ i ， j ），设 xij=0 把源点标记为∞， - ，再把源点加入到空队列 Q中 While not Empty(Q) do i ← Front(Q);Dequeue(Q) for 从 i 到 j 的每条边 do// 前向边 if j 没有被标记 rij ← uij - xij ifrij 0 Lj min{Li,xji}; 用 L，i- 来标记 j Enqueue(Q,j) If 汇点被标记了 沿着找到的增益路径进行增量 j ←n// 从汇点开始，用第二个标记反向移动 while j!=i // 没有到达源点 if 顶点 j 的第二个标记是 i+ xij ←xij+Ln else // 顶点 j 的第二个标记是 i- xji ←xji-Ln j ← i ； i ← i 的第二个标记指出的顶点 除了源点，擦去所有顶点的标记 用源点对 Q重新初始化 return x // 当前流量是最大的 思路以及代码解释： （全部源代码见附件） 先创建一个解决问题的类，命名为 G。 计算最大流作为这个类中的一个方法来实现。 利用二维数组 Map[i,j] 和 Flow[i,j] 分别存放容量和流量。 添加头文件 #include queue，后面需要用到队列，需要该类的取队首元素，加入队尾元素等方法。 class G { public: G(); G(intn,intstart,int end); void Edge(inta,intb,int flow); // 顶点 a 和顶点 void Maxflow(); // 计算最大流 private: int N; // 顶点个数 int Start; // 源点 int End, // 汇点 **Map, // 网络容量 **Flow, // 通过流量 **Rest, // 剩余流量 *Pre, // 标记流向 , 正为前向 , 负为后向 *Sign, // 顶点是否标记 ,0 为未标记 ,1 为已标记 *P; // 过程变量 , 记录流量 boolSignN(); // 标记顶点 int Min(inta,int b); // 计算最小值 void Update(); // 更新网络  b 之间的流量 }; 构造函数就先定义两个 G::G() {Pre=NULL;} G::G(int n,intstart,int end) { 初始化 }  // 不带参数的构造函数 // 带三个参数的构造函数，顶点个数，源点和汇点 在类 G中，实现了 void Maxflow(); 方法，用来计算最大流，其中标记顶点的函数定义为 boolSignN(); bool G::SignN()  // 标记顶点 { Update();  //