求最大流标号法的描述
求最大流标号法的描述
⑴数据结构
Const maxn=<网络顶点数>
Type node=record {可增广道路的顶点类型}
l,p:integer；{第一标号，检查标号}
end;
arc=record {网络边类型}
c,f:integer; {容量，流量}
end;
gtype=array[0..maxn,0..maxn] of arc；{网矩阵}
ltype=array[0..maxn] of node; {可增广道路}
var lt:ltype; {可增广道路}
g:gtype; {网络}
n,s,t:integer; {顶点数，源点，汇点}
⑵主要算法
①初始化网络，可增广道路
procedure read-graph；
var I,j:integer;
begin
readln(n); {顶点数}
fillchar(g,sizeof(g),0); {初始化网络}
fillchar(lt,sizeof(lt),0); {初始化可增广道路}
for i:=1 to n do
for j:=1 to n do
read(g[I,j].c);
end;
②寻找已标号而来检查的顶点序号
function check:integer;
var i:integer;
begin
i:=1;
while (i<=n)and not((lt[i].l<>0)and(lt[i].p=0)) do inc(i);
if i>n then check:=0 {顶点不存在}
else check:=i;
end;
③标号过程，并返回是否找到可增广道路及改进量a
function ford(var a:integer):boolean; {无增广道路返回true}
var I,j,m,x:integer;
begin
ford:=true;
fillchar(lt,sizeof(lt),0); {去掉原来的标号}
lt[s].l:=s; {从Vs开始}
repeat
１
i:=check; {寻找一个已标号而未检查的顶点i}
if i=0 then exit; {若该顶点不存在，则退出过程，返回true}
for j:=1 to n do
if (lt[j].l=0)and((g[I,j].c<>0)or(g[j,i].c<>0)
{寻找与Vi相邻且未标号的顶点j}
then begin
if (g[I,j].f if (g[j,i].f>0) then lt[j].l:=-I; end; lt[i].p:=1; {顶点Vi置已检查标志} until (lt[t].l<>0) {直到汇点Vt标号为止} m:=t; a:=maxint; {从Vt倒推，改进量a赋初值} repeat {求a} j:=m; m:=abs(lt[t].l); if lt[j].l<0 then x:=g[j,m].f; if lt[j].l>0 then x:=g[m,j].c-g[m,j].f; if a>x then a:=x; until m=s; {直至例推到顶点Vs为止} ford:=false; {返回可增广道路存在标志false} end; ④修正流量 procedure fulkerson(a:integer); var m,j:integer; begin m:=t; {以顶点Vt出发，逆向沿可增广道路修正容量} repeat j:=m; m:=abs(lt[j].l); if lt[j].l<0 then g[j,m].f:=g[j,m].f-a; {后向边p-} if lt[j].l>0 then g[m,j].f:=g[m,j].f+a; {前向边p+} until m=s; end; ⑤输出所有弧的流量 procedure answer; var I,j:integer; begin for i:=1 to n do for j:=1 to n do writeln(‘(’,I, ‘,’,j, ‘)’, ‘ ’,g[I,j].f) end; ⑥算法合成 procedure proceed; {求最大流} var d:integer; success:boolean; begin ２ s:=1; t:=n; {假设源点为V1，汇点为Vn} repeat success:=ford(d); {寻找可增广道路及改进量d} if success then answer {增广道路不存在，输出最大流} else fulkerson(d) {沿增广道路修正流量} until success; end; ⑦主程序 begin read_graph; {输入网} proceed; {求最大流} end. ３ //标号法求网络最大流量 #include 网络最大流问题 一产生背景 流量问题在实际中是一种常见的问题，在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题,控制系统中的信息流问题，常见的人流，物流，水流，气流，电流，现金流等。在一定条件下,求解给定系统的最大流量,就是网络最大流问题.网络系统最大流问题是图与网络理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。 二基本概念与定理 设cij为弧（i，j）的容量，fij为弧（i，j）的流量。容量是弧（i，j）单位时间内的最大通过能力，流量是弧（i，j）单位时间内的实际通过量，流量的集合f={fij}称为网络的流。发点到收点的总流量记为v=v(f)。 设D=(V,A)是一有向图且对任意E均有容量cij =（vi，vj），记C={cij︱（vi，vj）∈A},此外D中只有一个源vs和汇vt( 即D中与vs相关联的弧只能以vs为起点，与vt相关联的弧只能以vt为终点)，则称D=(V,A,C, vs,vt)为一网络。 引例1：图1给出了一张网络，其中：vs为源，vt为汇，弧旁的数字为该段弧的容量cij与流量fij，则显然有0≤fij ≤ cij 。 v2 （3,3) v4 （3,3）（5,5） vt (2,2) (2,2) (2,2) vt (6,4) (6,2) v1 (6,6) v3 图1 最大流问题可以建立如下形式的线性规划数学模型。图1最大流问题的线性规划数学模型为 12 max 0(,)0s s ij ij j i ij ij v f f f f i s t f c =+?-=≠???≤≤?∑∑所有弧(i,j) 由线性规划理论知，满足式上式的约束条件的解{fij}称为可行解，在最大流 问题中称为可行流。 可行流满足下列三个条件： (1)0(2)(3)i j i j m j i m j i sj it vs vt f c f f v f f ≤≤===∑∑∑∑ 条件（2）和条件（3）也称为流量守恒条件。 另外对有多个发点和多个收点的网络,可以另外虚设一个总发点和一个总收 点,并将其分别与各发点、收点连起来（图*），就可以转换为只含一个发点和一 个收点的网络。 S T S* T* 图* 所以一般只研究具有一个发点和一个收点的网络 在图D 中，从发点到收点的一条路线称为链，从发点到收点的方向规定为 链的方向。与链的方向相同的弧称为前向弧，前向弧集合记为u+ ，与链的方向 相反的弧称为后向弧，后向弧集合记为u-。 设f 是一个可行流，如果存在一条从发点vs 到收点vt 到的链u 满足： （1）所有前向弧上fij ＜cij 例题最大流的标号法 例2用标号法求下图所示的公路交通网络的最大流量（要求写出标号过程并说明得到的的确是最大流），其中，弧旁的数字是（q,f j）。. 解： ⑴首先，给V s标上（0,） ⑵检查v s,给v s为起点的未饱和弧的未标号的终点V2标号（V s,l（V2））,其中其它点不符合标号条件。 （3）检查V2，给V2为终点的非零流弧的未标号的起点V3标号（V2,l（V3））,其中其它点不符合标号条件。 ⑷检查V3，给V3为起点的未饱和弧的未标号的终点V4、V标号（V4,l（V4））、 （V6,l（V6））其中，1他）min[?3）234 彳34】min[ 4,5 4] 1 其它点不符合标号条件。 ⑸检查V6，给V6为起点的未饱和弧的未标号的终点V t标号（V t,l（V t））其中， 其它点不符合标号条件。 由于V t已标号，反向搜索可得增广链｛（V s,V2）,（V3,V2）,（V3,V6）, （V6,V t）｝，在该增 广链的前相弧（V s,V2）,（V3, V6）,（V6, V t）上增加l（V t） 4，在后向弧（V3,V2）上减去l（V t）4，其它弧上的流量不变，则可得一流量v（f） 20的新的可行流如下图。 V3 (5,5) V6 重新开始标号： ⑹首先，给V s标上（0,） ⑺检查V s,给V s为起点的未饱和弧的未标号的终点V2标号（V s,l（V2））,其中其它点不符合标号条件。 (8)检查V2，没有以V2为起点的未饱和弧的未标号终点和以V2为终点的非零流弧的未标号起点，因此不能增加标号点，标号进行不下去了，所以该可行流必为最大流，最大流的流量为v(f)=20。 事实上，可令V {V s，V2},V i {V3，V4,V5，V6，V t}，则最小截集(V i,V i)的截量 C(V i,V i) C s3 C25 C24 9 5 6 20 V( f)。 网络流算法 在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。 ［问题描述］如图4-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。 一、基本概念及相关定理 1)网络与网络流 定义1 给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点， 对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图4-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。 所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图4-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。 2)可行流与最大流 在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有： 定义2 满足下列条件 (1)容量约束：0≤fij≤cij，(vi,vj)∈E， (2)守恒条件 对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。 网络N中流值最大的流f*称为N的最大流。 3)可增广路径 所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。 定义3 设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件： 给定一个有向图D=(V,A)，在V中指定一点称为发点（记为），该点只有出发去的弧，指定另一点称为收点（记为），该点只有指向它的弧，其余的点叫做中间点。对于A中的每一条弧，对应一个数（简记），称之为弧的容量。通常我们把这样的D叫做网络，记为D=(V,A,C)。 （2）网络流：在弧集A上定义一个非负函数。是通过弧的实际流量，简记，称是网络上的流函数，简称网络流或流，称为网络流的流量。 §4 网络最大流问题 网络最大流问题是网络的另一个基本问题。 许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。 4.1 基本概念与定理 1．1．网络与流 定义14 （1）网络： 例1如图7-20是连结某产品产地和销地的交通图。弧表示从 到的运输线，弧旁的数字表示这条运输线的最大通过能力，括号内的数字表示该弧上的实际流。现要求制定一个运输方案，使从运到的产品数量最多。 可行流与最大流 在运输网络的实际问题中，我们可以看出，对于流有两个基本要求： 一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）； 二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。 因此有下面所谓的可行流的定义。 定义14对于给定的网络D=（V,A,C）和给定的流，若满足下列条件： （1）容量限制条件：对每一条弧，有 (7.9) （2）平衡条件： 对于中间点： 流出量=流入量，即对于每一个i (i≠s,t)，有 (7.10) 对于出发带点，有 (7.11) 对于收点，有 (7.12) 则称为一个可行流，称为这个可行流的流量。 注意，我们这里所说的出发点是指只有从发出去的弧，而没有指向的弧； 收点是指只有弧指向，而没有从它的发出去的弧。 数据结构与算法课程实验报告实验四：图的相关算法应用 姓名：王连平 班级：09信科2班 学号：I09630221 实验四图的相关算法应用 一、实验内容 求有向网络中任意两点之间的最短路。 二、实验目的 掌握图和网络的定义，掌握图的邻接矩阵、邻接表和十字链表等存储表示。掌握图的深度和广度遍历算法，掌握求网络的最短路的标号法和floyd算法。 三、问题描述 对于下面一张若干个城市以及城市间距离的地图，从地图中所有可能的路径中求出任意两个城市间的最短距离及路径，给出任意两个城市间的最短距离值及途径的各个城市。 四、问题的实现 4.1数据结构的抽象数据类型定义和说明 1） typedef struct ArcCell{//储存弧信息 int Distance; ArcCell *info;//此项用来保存弧信息，，在本实验中没有相关信息要保存 }ArcCell,AdjMatrix[ MAX_VERTEX_NUM][ MAX_VERTEX_NUM]; typedef struct{//储存顶点信息 string vexs[ MAX_VERTEX_NUM];//顶点向量 AdjMatrix arcs;//邻接矩阵 int vexnum , arcnum;//图的当前顶点数和弧数 }MGraph; 顶点信息和弧信息都是用来建立一个有向网G 2） d[v][w];//G中各对顶点的带权长度 若P[v][w][u]为TRUE，则u是从v到w当前求得最短路径上的顶点 4.2主要的实现思路 首先通过一个函数（CreateDN）建立图的邻接矩阵储存方式,一次输入某条弧的起点，终点，和权值。通过调用Locate函数来找到该弧在邻接矩阵中的相应位置。 其次运用弗洛伊德算法来求各定点的最短路劲，具体思路为：如果从v到w有弧，则存在一条长度为arcs[v][w]的路径，该路径不一定是最短路径。考虑路径（v,u,w）是否存在，若存在，比较（v,w）和（v,u,w）的长度，取较短者为从v到w的中间点序号不大于0的最短路径。以此类推，每次增加一个点，从而求出任意两点间的最短路径。这样，经过n次比较后，所求得的必为从v到w的最短路径。按此方法，可以同时求得任意两点间的最短路径。 五、主要源程序代码（包含程序备注） #include 例题 最大流的标号法 例2用标号法求下图所示的公路交通网络的最大流量（要求写出标号过程并说明得到的的确是最大流），其中，弧旁的数字是（c ij ,f ij ）。 . v 2 （5,5） v 5 （6,6） (2,2) （12,7） （15,7） v s （4,4） (4,4) v t (5,4) v 4 (4,4) （9,9) (10,5) v 3 (5,1) v 6 解： (1) 首先,给v s 标上(0,) (2) 检查v s ，给v s 为起点的未饱和弧的未标号的终点v 2标号(v s ,),其中 其它点不符合标号条件。 (3) 检查，给为终点的非零流弧的未标号的起点标号(,),其中 其它点不符合标号条件。 (4) 检查，给为起点的未饱和弧的未标号的终点标号(,)、(, )其中， 其它点不符合标号条件。 (5) 检查，给为起点的未饱和弧的未标号的终点标号(,)其中， 其它点不符合标号条件。 由于已标号，反向搜索可得增广链，在该增广链的前相弧上增加，在后向弧上减去，其它弧上的流量不变，则可得一流量的新的可行流如下图。 v 2 （5,5） v 5 （6,6） (2,2) （12,7） （15,11） v s （4,0） (4,4) v t (5,4) v 4 (4,4) （9,9) (10,9) v 3 (5,5) v 6 重新开始标号： (6) 首先,给v s 标上(0,) (7) 检查v s ，给v s 为起点的未饱和弧的未标号的终点v 2标号(v s ,),其中 ∞+)(2v l 2v 2v 3v 2v -)(3v l 3v 3v 64v v 、4v )(4v l 6v )(6v l 1]45,4m in[]),(m in[)(343434=-=-=f c v l v l 6v 6v t v t v )(t v l t v )},(),,(),,(),,{(663232t s v v v v v v v v =μ),(),,(),,(6632t s v v v v v v 4)(=t v l ),(23v v 4)(=t v l 20)(=f v ∞+)(2v l 最短路径问题的研究 学生姓名：苏振国指导老师：王向东 摘要最短路径问题是研究线状分布的地理事物中最常用的方法。其中迪克斯查1959年提出的标号法在最短路径问题的研究中应用最为广泛，尤其在交通选址方面。根据迪克斯查标号法的基本思想及应用现状，本文以其在城市消防站选址问题上的应用为例，详细介绍了迪克斯查标号法的应用、原理及其步骤。展现了最短路径法的突出优点：不仅求出了起点和终点的最短路径及其长度，而且求出了起点到图中其他各点的最短路径及其长度。 关键词最短路径步骤原理应用分类 1引言 在实际中常提出这样的问题，比如说，在交通网中，问A，B两地是否有道路可通?如果有通路且不止一条的话，那么最短的是哪条?所谓最短，可理解为里程数最少，也可理解为旅差费最省，还可理解为道路的建造成本最低等等。总之，这类问题都可归结为在一个有向图中求最短路径的问题。本论文研究的主要目的就是为了详细介绍关于最短路径问题的标号法，及其在实际生活中如何应用。下面我将展开论述。 2最短路径的现状分析及其研究发展方向 2.1现状分析 最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的一个研究热点。国内外大量专家学者对此问题进行了深入研究。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。它们在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色。针对串行计算机的最短路径算法,已经几乎到达理论上的时间复杂度极限。现在的研究热点,一是针对实际网络特征优化运行结构,在统一时间复杂度的基础上尽可能地提高算法的运行效率;二是对网络特征进行限制,如要求网络中的边具有整数权值等,以便采用基数堆等数据结构设计算法的运行结构;三是采用有损算法,如限制范围搜索、限定方向搜索及限制几何层次递归搜索;四是采用拓扑层次编码路径视图,对最短路径进行部分实例化编码存储;五是采用并行算法,为并行计算服务。 2.2研究发展方向 2.2.1最短路径算法的实时性 目前,静态的最短路径算法已经十分完善。但是,在实践中,网络特征可能时刻会发生变化,要求最短路径算法必须能够实时地自动更新。这类问题主要集中在交通网络的实时导航、通勤、调度和计算机互联网的数据传递路由等方面。在动态最短路径问题中,弧段权值、节点耗费等均为时间t的函数,既可以是连续的,也可以是离散的。在假定网络路径权值服从FIFO原则的一致性假设前提下,任何静态的LS和LC算法均可扩展为时间依赖的最短路径算法。 2.2.2最短路径算法的并行化 随着计算机处理数据量的逐渐增多,传统的串行计算机的负荷也逐渐加重。运行在服务 从一道题目的解法试谈网络流的构造与算法 福建师大附中江鹏 1. 引论 A. 对网络流算法的认识 网络流算法是一种高效实用的算法，相对于其它图论算法来说，模型更加复杂，编程复杂度也更高，但是它综合了图论中的其它一些算法（如最短路径），因而适用范围也更广，经常能够很好地解决一些搜索与动态规划无法解决的，看似NP的问题。 B. 具体问题的应用 网络流在具体问题中的应用，最具挑战性的部分是模型的构造。这没用现成的模式可以套用，需要对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），并且归纳总结一些经验，发挥我们的创造性。 2. 例题分析 【问题1】项目发展规划（Develop） Macrosoft?公司准备制定一份未来的发展规划。公司各部门提出的发展项目汇总成了一张规划表，该表包含了许多项目。对于每个项目，规划表中都给出了它所需的投资或预计的盈利。由于某些项目的实施必须依赖于其它项目的开发成果，所以如果要实施这个项目的话，它所依赖的项目也是必不可少的。现在请你担任Macrosoft?公司的总裁，从这些项目中挑选出一部分，使你的公司获得最大的净利润。 ●输入 输入文件包括项目的数量N，每个项目的预算Ci和它所依赖的项目集合Pi。格式如下：第1行是N； 接下来的第i行每行表示第i个项目的信息。每行的第一个数是Ci，正数表示盈利，负数表示投资。剩下的数是项目i所依赖的项目的编号。 每行相邻的两个数之间用一个或多个空格隔开。 ●输出 第1行是公司的最大净利润。接着是获得最大净利润的项目选择方案。若有多个方案，则输出挑选项目最少的一个方案。每行一个数，表示选择的项目的编号，所有项目按从小到大的顺序输出。 ●数据限制 0≤Ｎ≤1000 -1000000≤Ci≤1000000 ●输入输出范例 案例BMZ公司的最大流问题 背景 BMZ 公司是欧洲一家生产豪华汽车的制造商。它因为提供优质的服务而获得很好的声誉，保持这个声誉一个很重要的秘诀就是它有着充裕的汽车配件供应，从而能够随时供货给公司众多的经销商合授权维修店。 这些供应件主要存放在公司的配送中心里，这样一有需求就可以立即送货。卡尔（BMZ 公司的供应链的经理）优先考虑的是改进这些配送 中心的不足之处。 该公司在美国有几个配送中心。但是，离洛杉机中心最近的一个配送中心却坐落离洛杉机1000 多英里的西雅图。保证洛杉机中心良好的供应是尤为重要的。因此，现在那里的供应不断减少的现状成为了公司高层管理真正关心的问题。 大部分的汽车配件以及新车是在该公司坐落于德国的斯图加特的总 厂和新车一起生产的。也就是这家工厂向洛杉机中心供应汽车配件。每月有超过300000 立方英尺的配件需要运到。现在，下个月需要多得多的数量以补充正在减少的库存。 问题 卡尔需要尽快制定一个方案，使得下个月从总厂运送到洛杉机配送中心的供应件尽可能多。他认识到了这是个最大流的问题——一个使得从总厂运送到洛杉机配送中心的配件流最大的问题。因为总厂生产的配件量远远要大于能够运送到配送中心的量，所以，可以运送多少配件的限制条件就是公司配送网络的容量。 这个配送网络如下图1 。在图中，标有ST 和LA 的节点分别代表斯图加特的工厂和洛杉机的配送中心。由于工厂所在地有一个铁路运转点，所以首先通过铁路把配件运输到欧洲的三个港口：鹿特丹（RO ）波尔多（BO ）和里斯本(LI) ；然后通过船运到美国的港口纽约（NY ）或新奥尔良（NO ）；最后用卡车送到洛杉机的配送中心。 图1 网络模型 例题最大流的标号法集团标准化办公室：[VV986T-J682P28-JP266L8-68PNN] 例题 最大流的标号法 例2用标号法求下图所示的公路交通网络的最大流量（要求写出标号过程并说明得到的的确是最大流），其中，弧旁的数字是（c ij ,f ij ）。 . v 2 （5,5） v 5 （6,6） (2,2) （12,7） （15,7） v s （4,4） (4,4) v t (5,4) v 4 (4,4) （9,9) (10,5) v 3 (5,1) v 6 解： (1)首先,给v s 标上(0,) (2)检查v s ，给v s 为起点的未饱和弧的未标号的终点v 2标号(v s ,),其中 其它点不符合标号条件。 (3)检查，给为终点的非零流弧的未标号的起点标号(,),其中 其它点不符合标号条件。 (4)检查，给为起点的未饱和弧的未标号的终点标号(,)、(,)其中， 其它点不符合标号条件。 (5)检查，给为起点的未饱和弧的未标号的终点标号(,)其中， 其它点不符合标号条件。 由于已标号，反向搜索可得增广链，在该增广链的前相弧上增加，在后向弧上减去 ，其它弧上的流量不变，则可得一流量的新的可行流如下 图。 v 2 （5,5） v 5 （6,6） (2,2) （12,7） （15,11） v s （4,0） (4,4) v t (5,4) v 4 (4,4) （9,9) (10,9) v 3 (5,5) v 6 ∞+)(2v l 2v 2v 3v 2v -)(3v l 3v 3v 64v v 、4v )(4v l 6v )(6v l 1]45,4m in[]),(m in[)(343434=-=-=f c v l v l 6v 6v t v t v )(t v l t v )},(),,(),,(),,{(663232t s v v v v v v v v =μ),(),,(),,(6632t s v v v v v v 4)(=t v l ),(23v v 4)(=t v l 20)(=f v 分类号 密级 编号 2015届本科生毕业论文 题目基于AHP决策分析法和Dijkstra 算法的最短路径 学院资源与环境工程学院 姓名杜玉琪 专业地理科学 学号20111040205 指导教师王荣 提交日期2015年5月8日 原创性声明 本人郑重声明：本人所呈交的论文是在指导教师的指导下独立进行研究所取得的成果。学位论文中凡是引用他人已经发表或未经发表的成果、数据、观点等均已明确注明出处。除文中已经注明引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。 本声明的法律责任由本人承担。 论文（设计）作者签名： 指导老师签名： 签名日期: 2013 年 5 月18 日 目录 0 引言 (3) 1 研究区概况 (4) 2.数据来源与研究方法 (4) 2.1数据来源 (4) 2.2研究方法 (5) 2.2.1AHP决策分析方法 (5) 2.2.2Dijkstra算法 (6) 3实例分析 (7) 3.1 基于AHP对3A级景区决策分析 (7) 3.1.1层次结构模型的构造 (7) 3.1.2模型计算过程 (8) 3.1.3结果分析 (10) 3.2基于Dijkstar算法对3A级景点旅游路线的设计 (10) 3.2.1旅游路线模型构造 (10) 3.2.2模型计算与分析 (13) 4结语 (13) 参考文献 (14) 致谢 (15) 基于AHP决策分析法和Dijkstar算法的最短路径分析 ——以天水市3A级旅游景点为例 杜玉琪 (天水师范学院资源与环境工程学院甘肃天水741000） 摘要：随着西部旅游业的发展，旅游最佳路线的选择变得越来越重要。本文运用AHP决策分析的方法进行综合评价分析天水市众多旅游景点中的麦积石窟、伏羲庙、玉泉观、南郭寺、大象山、武山水帘洞、清水温泉，这7个3A级景点各自的旅游价值。再通过Dijkstar算法，对上述旅游景点的最短旅游路线的选择进行研究，最终为不同要求的游客提供出最佳的旅游路线。 关键字：AHP决策分析；Dijkstar算法；最短路径分析；天水市 Based on the AHP decision analysis method and the analysis of Dijkstar algorithm of the shortest path ——in tianshui 3 a-class tourist attractions as an example Abstract：With the development of the western tourism, tourism optimal route choice is becoming more and more important.This article applies the method of AHP decision analysis on comprehensive evaluation analysis of the numerous tourist attractions tianshui wheat product, yuquan view, nanguo temple grottoes, fu xi temple, the elephant, wushan waterfall cave, water hot springs, the seven aaa scenic spot tourism value. Again through the Dijkstra algorithm, the choice of the tourist attractions of the shortest travel route, finally for different requirements of the best travel route for tourists. Key words: Analytic hierarchy process; Dijkstar; Shortest path; tianshui city 0 引言 随着西部旅游业如火如荼的发展，天水市自驾旅游开始被越来越多的人选择。自驾车旅游者追求以最少的花销走更远的路，看更优美的风景。因此设计出一条多景点间距离最短（或费用，时间最少）的旅游线路是自驾车游客的现实需求[1]。而对于旅游景点的评价及旅游线路的选择问题,是旅游学术界一直关注的课题。众多学者所采用的方法，大体可归纳为主观定性评价和客观定量评价。景点评价方法在我国开展的时间并不长，主要侧重定性描述，较缺乏定量 例题 最大流的标号法 例2用标号法求下图所示的公路交通网络的最大流量（要求写出标号过程并说明得到的的确是最大流），其中，弧旁的数字是（c ij ,f ij ）。 . v 2 （5,5） v 5 （6,6） (2,2) （12,7） （15,7） v s （4,4） (4,4) v t (5,4) v 4 (4,4) （9,9) (10,5) v 3 (5,1) v 6 解： (1) 首先,给v s 标上(0,∞+) (2) 检查v s ，给v s 为起点的未饱和弧的未标号的终点v 2标号(v s ,)(2v l ),其中 其它点不符合标号条件。 (3) 检查2v ，给2v 为终点的非零流弧的未标号的起点3v 标号(2v -,)(3v l ),其中 其它点不符合标号条件。 (4) 检查3v ，给3v 为起点的未饱和弧的未标号的终点64v v 、标号(4v ,)(4v l )、(6v ,)(6v l )其中，1]45,4m in[]),(m in[)(343434=-=-=f c v l v l 其它点不符合标号条件。 (5) 检查6v ，给6v 为起点的未饱和弧的未标号的终点t v 标号(t v ,)(t v l )其中， 其它点不符合标号条件。 由于t v 已标号，反向搜索可得增广链)},(),,(),,(),,{(663232t s v v v v v v v v =μ，在该增广链的前相弧),(),,(),,(6632t s v v v v v v 上增加4)(=t v l ，在后向弧),(23v v 上减去4)(=t v l ，其它弧上的流量不变，则可得一流量20)(=f v 的新的可行流如下图。 v 2 （5,5） v 5 （6,6） (2,2) （12,7） （15,11） v s （4,0） (4,4) v t (5,4) v 4 (4,4) （9,9) (10,9) v 3 (5,5) v 6 重新开始标号： (6) 首先,给v s 标上(0,∞+) (7) 检查v s ，给v s 为起点的未饱和弧的未标号的终点v 2标号(v s ,)(2v l ),其中 其它点不符合标号条件。 数据通信与计算机网络大作业 Dijkstra 最 短 路 径 算 法 【摘要】 摘要:最短路径分析在地理信息系统、计算机网络路由等方面发挥了重要的作用, 对其进行优化很有必要。本文分析了传统 的最短路径算法(即Dijkstra 算法)的优化途径及现有的优化算法, 然后在Dijkstra 算法的基础上, 采用配对堆结构来实现路 径计算过程中优先级队列的一系列操作, 经理论分析与实验测试结果对比, 可以大大提高该算法的效率和性能。 【关键词】 最短路径; Dijkstra 算法; 【正文】 随着计算机网络技术和地理信息科学的发展, 最短路径问题无论是在交通运输, 还是在城市规划、物流管理、网络通讯等方面, 它都发挥了重要的作用。因此, 对它的研究不但具有重要的理论价值, 而且具有重要的应用价值。研究最短路径问题通常将它们抽象为图论意义下的网络问题, 问题的核心就变成了网络图中的最短路径问题。此时的最短路径不单指“纯距离”意义上的最短路径, 它可以是“经济距离”意义上的最短路径, “时间”意义上的最短路径, “网络”意义上的最短路径。关于最短路径问题, 目前所公认的最好的求解方法, 是由F.W.Dijkstra 提出的标号法, 即Dijkstra 算法。 1 Dijkstra 算法 Dijkstra 算法是求最短路径的最基本和使用最广泛的算法。在求从网络中的某一节点(源点)到其余各节点的最短路径时, 经典Dijkstra 算法将网络中的节点分成三部分: 未标记节点、临时标记节点和最短路径节点(永久标记节点)。算法开始时源点初始化为最短路径节点, 其余为未标记节点, 算法执行过程中, 每次从最短路径节点往相邻节点扩展, 非最短路径节点的相邻节点修改为临时标记节点, 判断权值是否更新后, 在所有临时标记节点中提取权值最小的节点, 修改为最短路径节点后作为下一次的扩展源, 再重复前面的步骤, 当所有节点都做过扩展源后算法结束。具体算法描述如下: 设在一非负权简单连通无向图G= 最大流问题（标号法） function [f,wf,No]=max_flux(n,C) % 利用Ford--Fulkerson 标号法求最大流算法的MATLAB 程序代码 % f %显示最大流 % wf %显示最大流量 % No %显示标号, 由此可得最小割 % n 节点个数 % C %弧容量 f=zeros(n,n); %取初始可行流f 为零流 No=zeros(1,n); d=zeros(1,n); %No,d 记录标号 while(1) No(1)=n+1; d(1)=Inf; %给发点vs 标号 while(1) pd=1; %标号过程 for i=1:n if No(i) %选择一个已标号的点vi for(j=1:n) if No(j)==0&&f(i,j) No(j)=i;d(j)=C(i,j)-f(i,j); pd=0; if d(j)>d(i) d(j)=d(i); end elseif No(j)==0&&f(j,i)>0 %对于未给标号的点vj, 当vjvi 为非零流弧时 No(j)=-i; d(j)=f(j,i); pd=0; if d(j)>d(i) d(j)=d(i); end; end; end; end; end if No(n)||pd break; end; end %若收点vt 得到标号或者无法标号, 终止标号过程 if pd break; end %vt 未得到标号, f 已是最大流, 算法终止 dvt=d(n); t=n; %进入调整过程, dvt 表示调整量 while(1) if No(t)>0 f(No(t),t)=f(No(t),t)+dvt; %前向弧调整 elseif No(t)<0 f(No(t),t)=f(No(t),t)-dvt; end %后向弧调整 if No(t)==1 for i=1:n No(i)=0; d(i)=0; end; break; end %当t 的标号为vs 时, 终止调整过程 t=No(t); end; end; %继续调整前一段弧上的流f wf=0; for j=1:n wf=wf+f(1,j); end 开题报告 数学与应用数学 网络最大流问题算法研究 一、综述本课题国内外研究动态, 说明选题的依据和意义 最大流问题是指在一定的条件下, 要求流过网络的物流、能量流、信息流等流量为最大的问题[2]. 最大流问题已有50多年的研究历史, 这段时期内, 人们建立了最大流问题较 为完善的理论, 同时开发了大量优秀的算法. 如Ford 和Fulkerson 增截轨算法 [3]、Dinic 阻塞流算法、Goldberg 推进和重标号算法[6]以及Goldberg 和Rao 的二分长度阻塞流算法等等, 这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用. 近年来, 随着计算机科学技术和网络的快速发展, 网络最大流问题得到了更深入的研究, 并极大地推动了最大流问题的研究进展. 然而, 研究工作仍未结束: 首先, 在理论算法研究方面, 人们还没有发现最大流问题算法时间复杂度的精确下界, 更没有任何一个通用算法达到或接近问题的下界; 其次, 在算法的实际性能方面, 目前算法的实际性能也不能满足许多应用问题的要求; 同时,最大流问题作为特殊的线性规划问题, 它远比一般线性规划问题容易解决, 发现应用领域中的问题和最大流问题的联系可以使应用问题更好地得到解决. 因此, 关于网络最大流问题的研究具有十分重要的理论意义和实用价值[5]. 最早的算法是Dantzig 提出的网络单纯刑法和Ford 和Fulkerson 的增载轨算法, 他们都是伪多项式时间算法, 分别由Dinic, Edmonds 和Karp 等提出. 1973年Dinic 首次获得了时间复杂度的核心因子为nm 算法. 以后的几十年中, 最大流算法获得了很大的进展. 在最大流问题中, ()nm O 时间界是一个自然的障碍. 如果我们把一个流沿从源到汇的各个路径进行分解, 根据流分解定理, 这些包含流的路径的总长度为()nm Θ.因此, 对每次利用一条曾接轨的算法, ()nm O 时间是这类算法的下界. 尽管这个下界对使用动态树数据结构或基于预流概念的算法是不适用的, 但在很长一段时间内, ()nm O 的 139 §19. 利用Matlab 编程计算最短路径及中 位点选址 1、最短路问题 两个指定顶点之间的最短路径。 例如，给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。 以各城镇为图G 的顶点，两城镇间的直通铁路为图G 相应两顶点间的边，得图G 。对G 的每一边e ，赋以一个实数)(e w —直通铁路的长度，称为e 的权，得到赋权图G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点00,v u 间的具最小权的轨。这条轨叫做00,v u 间的最短路，它的权叫做00,v u 间的距离，亦记作),(00v u d 。 求最短路已有成熟的算法：迪克斯特拉（Dijkstra ）算法，其基本思想是按距0u 从近到远为顺序，依次求得0u 到G 的各顶点的最短路和距离，直至0v （或直至G 的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。 (i) 令0)(0=u l ，对0u v ≠，令∞=)(v l ，}{00u S =，0=i 。 (ii) 对每个i S v ∈（i i S V S \=），用 )} ()(),({min uv w u l v l i S u +∈ 代替)(v l 。计算)}({min v l i S v ∈，把达到这个最小值的一个顶点记为1+i u ，令 140 } {11++=i i i u S S 。 (iii). 若1||-=V i ，停止；若1||- 求最大流标号法的描述 ⑴数据结构 Const maxn=<网络顶点数> Type node=record {可增广道路的顶点类型} l,p:integer；{第一标号，检查标号} end; arc=record {网络边类型} c,f:integer; {容量，流量} end; gtype=array[0..maxn,0..maxn] of arc；{网矩阵} ltype=array[0..maxn] of node; {可增广道路} var lt:ltype; {可增广道路} g:gtype; {网络} n,s,t:integer; {顶点数，源点，汇点} ⑵主要算法 ①初始化网络，可增广道路 procedure read-graph； var I,j:integer; begin readln(n); {顶点数} fillchar(g,sizeof(g),0); {初始化网络} fillchar(lt,sizeof(lt),0); {初始化可增广道路} for i:=1 to n do for j:=1 to n do read(g[I,j].c); end; ②寻找已标号而来检查的顶点序号 function check:integer; var i:integer; begin i:=1; while (i<=n)and not((lt[i].l<>0)and(lt[i].p=0)) do inc(i); if i>n then check:=0 {顶点不存在} else check:=i; end; ③标号过程，并返回是否找到可增广道路及改进量a function ford(var a:integer):boolean; {无增广道路返回true} var I,j,m,x:integer; begin ford:=true; fillchar(lt,sizeof(lt),0); {去掉原来的标号} lt[s].l:=s; {从Vs开始} repeat １标号法求网络最大流量
最大流问题
例题最大流的标号法
网络流算法
网络最大流问题概论
实验四-图的最短路径(弗洛伊德算法实现)
例题最大流的标号法
最短路径问题
从一道题目的解法试谈网络流的构造与算法
运筹学-最大流- 案例
例题最大流的标号法
最短路径分析
例题最大流的标号法
dijkstra最短路径算法
最大流问题
网络最大流问题算法研究【开题报告】
§19利用Matlab编程计算最短路径及中位点选址
求最大流标号法的描述