运筹学图与计算机网络分析.ppt

一般的最短路问题描述： 给定一个赋权有向图D=(V,A)，对每一个弧a=(vi,vj)，相应地有权w(a)=wij，又给定D中的任何两个顶点vs和vt ，设P是从vs到vt的路，定义路P的权是P中所有弧之和，记为w(P)，最短路问题就是要在所有从vs到vt的路中，求一条权最小的路，即一条从vs到vt的路P0使得： 路P0的权称为从vs到vt的距离，记为d(vs,vt)。 有向图权值非负---- Dijkstra算法 Dijkstra算法的基本步骤(权值非负) 1.给顶点v1标号(0)，v1称为已标号点，记标号点集为V1={v1} 2.在未标号点集V2中找出与标号点集V1中的顶点vi有弧相连(并且以vi为起点)的点vj， 3.在第2步选出的点中，选出满足下面条件的点vk，并给vk标号(l,L1k)，其中l为第一标号， L1k为第二标号 为从v1到vk的最短路的长度，l表示在从v1到vk的最短路上，与vk相邻的点是vl 4. 若最后一个顶点vn未标号，则转回第2步；若vn已标号，则从vn开始，按照第一个标号逆向追踪，直到v1，就得到从v1到vn的最短路，vn的第二个标号表示最短路的长度。 求从v1到v8的最短路 (0) (1,1) (1,3) (3,5) (2,6) (5,10) (5,9) (5,12) 注：在给顶点编号时，如果在多个为标号点均取得最小值Llk则对这多个点同时标号，这些点的第二个标号相同，但是第一个标号不一定相同。 课堂练习： P225 6. a) 和 b) 有向图某些权值为负 1. 先对图中各个点按照Dijkstra算法标号，称之为第一次标号，令m=1，转入第二步； 2. 对图中除了v1以外的所有点进行m+1次标号，记L1k(m+1)为对顶点vk的第m+1次标号的第二个标号值，计算公式如下： 3.如果对所有的点L1k(m)= L1k(m+1)都成立则逆向追踪，找出最短路，算法终止；若存在L1k(m) L1k(m+1), 则令m=m+1，返回第2步 求从v1到v4的最短路 v1 v2 v3 v4 3 2 -2 -1 4 5 (0) v1 v2 v3 v4 3 2 -2 -1 4 5 (1,2) (1,3) (2,1) (0) v1 v2 v3 v4 3 2 -2 -1 4 5 (3,1) (1,3) (2,0) 课堂练习: P225 7 无向图 v1 v2 v3 v4 v5 2 3 1 4 1 5 3 将算法稍作修改：在未标号点集中 找出与标号点vi有边相连的点vj 网络最大流问题 下图表示从产地v1到销地v6的交通网，弧旁边的数字表示这条运输线的最大通过能力，产品经过这个交通网从v1运到v6，要求制定一个运输方案使得从v1运到v6的产品数量最多。 基本概念 网络与流 对有向图D=(V,A)，如果其中指定某一点vs为发点，另一点vt为收点，其他点则称为中间点。若对于有向图D中的每一条弧(vi,vj) ∈A，都有一个数c(vi,vj) ≥0与它对应，称c为弧的容量，记为D=(V,A ,C) 定义在弧集合A上的一个函数f={f(vi,vj)}称为网络D上的流，并称f(vi,vj)为弧(vi,vj)上的流量，简记为fij 可行流： 满足下述条件的流称为可行流： (1)容量限制：对于每一个弧(vi,vj) ∈A， 0≤fij ≤ cij (2)平衡条件： 对于中间点：流出量等于流入量，即对于每个i(i≠s,t)有 对于发点： 对于收点： 称v(f)为可行流的流量，发点的净输出量等于收点的净输入量。 最大流问题就是要找出一个可行流使得v(f)达到最大 饱和弧和非饱和弧 网络D=(V,A ,C)，f={f(vi,vj)}是D的可行流，则如果某一条弧(vi,vj) ∈A满足 (1) fij = cij ，则称(vi,vj)为饱和弧； (2) fij cij ， 则称(vi,vj)为非饱和弧； (3) fij =0 ， 则称(vi,vj)为零流弧； (4) fij 0 ， 则称(vi,vj)为非零流弧； 前向弧和后向弧 网络D中与给定的链 方向一致的弧 称为前向弧，记作 ； 与给定的链方向相反的弧称为后向弧，记作 ； 增广链(可扩充链) 4 0 0 2 1 大家想想：增广链的意义在哪里？ 根据定理，对于给定的可行流f，要判断它是不是最大流只需要判断D中有没有关于f的增广链。 如果有，则需要对f进行改进；如果没有增广链，则已经得到最大流。 定理：可行流f*是最大流，当且仅当不存在关于f*的增广链 寻找最大流的标号法 网络D中的点分为两类，一类是标号点(属于V1* )，一类是非标号点(不属于V1* ) ； 标号点有两类一类