图的最短路径及应用.ppt

图的最短路径及应用,最小生成树 最短路径算法 深入应用 wzl 2013-10-29,图的最小生成树,图的最小生成树主要两种方法：顶点遍历 （1） prim算法 图的存储矩阵、深搜算法、集合运算 （2）kruskal算法 边集数组存储、贪心算法、集合运算,prim算法的要点是： （1）设有n个顶点的连通网： G=（V，E），T=（U，TE）是G的最小生成树 其中U是顶点集 TE是T的边集 U、TE开始值为空,（2）算法如下： Procedure Prim(GA,CT); begin for I:=1 to n-1 do 给CT赋初值，对应第0次的LW值 CTI.from :=1 ; ctI.end: =I+1 ; ctI.w:=GA1, i+1 ; for k:=1 to n-1 do 进行n-1次循环，求出最小生成树的第K条边 min:=maxint ; m:=k ; for j:=k to n-1 do if ctj.w k then ctk 与ctm 的交换 将最短边调到第K单元 , j:=ctk.end; 将新的并入T中顶点给J for I:=k+1 to n-1 do 修改LW中的有关边 d:=ctI.end ; w:=GAj, d ; IF WCTI.W then CTi. w:=w; CTi.from:=j ; End;,Kruskal 算法 （ 贪心算法 ）,(1) 建立边集记录数组：起点、终点、边的权 (2) 按权的大小排序 (3) 每次选择最短边，且不构成回路，直到所有顶点都在这棵树上。 关键判断回路：用集合方法并查集 顶点查找、顶点集合并集构成边的两个顶点分别在不同的顶点集合中合并操作,算法： Procedure kruskal ( GE,C ) ; begin for i:=1 to n do si:= i ; 初始化顶点集合 i:=1 ; j:=1 i 表示边数，j 表示数组GE的下标 while i m2 then 生成树的一条边 ,being ci:=j ; 保存选取的第i条边 ,j 是GE数组的下标 i:=i+1 ; sm1:=sm1+sm2 ; sm2:= ; end; (3) j:=j+1 ; end ; 运行该程序后，C数组的值为： 1 2 3 4 5 所以最小生成树由GE数组中的1，2，3，5，7 边组成。,图的最短路径,(1) 深搜算法：递归算法思想回溯不输出过程 (2) 宽搜算法：队列算法判重 输出路径 (3) Dijktra 算法：单源最短路径 从一个顶点到另一个顶点的最短路径调整路径 可以输出路径，又称标号法 (4) floyed 算法 ： 任意两个顶点之间的最短路径调整路径,(5) 启发式搜索 在宽度优先搜索算法的基础上，每次并不是把所有可展开的结点展开，而是利用一个自己确定的估价函数对所有没展开的结点进行估价，从而找出最应该被展开的结点（也就是说我们要找的答案最有可能是从该结点展开），而把该结点展开，直到找到目标结点为止。 估价函数比较难确定,(6) 等代价搜索法 等代价搜索法也是在宽度优先搜索的基础上进行了部分优化的一种算法，它与启发式搜索的相似之处都是每次只展开某一个结点（不是展开所有结点），不同之处在于：它不需要去另找专门的估价函数，而是以该结点到起点的距离作为估价值，也就是说，等代价搜索法是启发式搜索的一种简化版本。 (7) 递推法 该算法的中心思想是：任意两点i,j间的最短距离（记为Dij）会等于从i点出发到达j点的以任一点为中转点的所有可能的方案中，距离最短的一个。即： Dij = min Dij , Dik+Dkj ，1=k=n。,类似动态规划的表达式，用二维数组存放任意两点间的最短距离，利用上述公式不断地对数组中的数据进行处理，直到各数据不再变化为止，这时即可得到A到E的最短路径。 Di表示起点到i的最短路长度，g是邻接矩阵，s表示起点； 1、Di:=gs,i (1Dk+gk,j then begin Dj:= Dk+gk,j; c:=true; end; Until not c；,该算法过程：不断地求一个数字最短距离矩阵中的数据的值，而当所有数据都已经不能再变化时，就已经达到了目标的平衡状态，这时最短距离矩阵中的值就是对应的两点间的最短距离。 （8）动态规划 某些最短路径问题也可以用动态规划来解决，通常这类最短路径问题所对应的图必须是有向无回路图。 动态规划算法与递归算法不同之处在于它们的算法表达式： 递归：类似f(n)=x1*f(n-1)+x2*f(n-2)确定关系表达式； 动态规划：f(n)=min(f(n-1)+x1,f(n-2)+x2)，即无法找到确定关系的表达式，只能找到一个不确定关系的表达式，f(n)的值是动态的，随着f(n-1),f(n-2)等值的改变而确定跟谁相关。,（9）标号法 标号法是一种非常直观的求最短路径的算法，可以用一个数轴简单地表示这种算法： 以A点为0点，展开与其相邻的点，并在数轴中标出。, 因为C点离起点A最近，因此可以断定C点一定是由A直接到C点这条路径是最短的（因为A、C两点间没有其它的点，所以C点可以确定是由A点直接到达为最短路径）。因而就可以以已确定的C点为当前展开点，展开与C点想连的所有点A、B、D、E。, 由数轴可见，A与A点相比，A点离原点近，因而保留A点，删除A点，相应的，B、B点保留B点，D、D保留D，E、E保留E，得到下图：, 此时再以离原点最近的未展开的点B联接的所有点，处理后，再展开离原点最近未展开的D点，最终结果： 结论：点C、B、D、E就是点A到它们的最短路径（注意：这些路径并不是经过了所有点，而且到每一个点的那条路径不一定相同）。因而A到E的最短距离就是13。经过了哪几个点，在过程中加以记录即可。,标号法是一种求图的最短路径的不用重复回溯搜索的高效率算法。算法思想 在图G中，顶点Vi到Vj的非负长度为Map(i, j)，求从起点Vs到终点Ve的最短距离。 设：x数据为扩展的队列；Sum(j)表示顶点Vs到Vj的最短距离，FA(j)表示顶点Vj前趋结点，算法过程： （1）队列初始化,Vs进入队列L, X1:=s, sum1=0； （2）取队首结点VK，若VK是目标结点Ve，则输出结果（最短路径值及路径）程序结束；否则继续（3）；,（3）由VK扩展出结点VJ（结点VK与VJ相连），计算代价值 若Sum(k)+mapk,jsum(j) 则替换结点J的代价，换代价值由小到大插入队列，并记录其父结点：sum(j):=sum(k)+mapk,j, faj:=k，结点J入队列继续（2），否则直接转（2）。 注意： 1.只有两个顶点间距离为非负时，才可用标号法。 2.只有队列的首结点是目标结点时，才可停止计算。否则得出的不一定是最优解。 标号法算法伪代码如下：,fillchar(x,sizeof(x),0); for I:=1 to n do begin sumI:=maps,I; faI:=s; end; x1:=s; sums:=0; f:=1; r:=1; fas:=0; repeat temp:=xf; if temp=Ve then print ; halt; for j:=1 to n do if (sumtemp+maptemp,j0 ) then begin sumj:=sumtemp+maptemp,j; r:=r+1; faj:=f; end; f:=f+1; until f r,例题1、特快专递 加国是个小国，仅有n个城市( 1n40)。奥维尔负责这个国家的特快专递，他有一辆汽车沿途他要到各个城市去送ems信件，各城市之间的路程s ( 0s1000) 是已知的，且A城市到B城市与B城市到A城市的路程大多不同。为了提高效率，他从快递公司出发到每个城市一次，然后返回快递公司所在城市，假设快递公司所在的城市为1，他不知道选择什么样的路线才能使所走的路程最短。请你帮助他选择一条最短的路。,输入：城市数n 和各城市之间的路程（均是整数） 输出：最短的路径 样例：salesman.in 3 0 2 1 1 0 2 2 1 0 salesman.out 3,算法： 求最短路径算法，所要注意的问题： 他需要返回到初始的城市,Program salesma; Var g:array140,140 of integer; a:array140 of integer; v:array140 of boolean; n,i,j,q:integer; s,t,min:longint; Procedure try(p:integer); var i:integer; begin if q=n+1 then begin if s+gp,1min then min:=s+gp,1; exit; end;,for i:=2 to n do if not(vi) then begin inc(s,gp,i);vi:=true;inc(q); if smin then try(i); dec(s,gp,i); vi:=false;dec(q); end; end; Procedure work; var i,j,k,p,l:integer; v:array140 of boolean;,begin fillchar(v,sizeof(v),false); l:=1; min:=0; for i:=2 to n do begin k:=2; while vk do inc(k); p:=k; for j:=p+1 to n do if not(vj) and (gl,jgl,k) then k:=j; inc(min,gl,k); l:=k;vl:=true; end; inc(min,gl,1); end;,begin assign(input,salesma.in);reset(input); assign(output,salesma.out);rewrite(output); read(n); for i:=1 to n do for j:=1 to n do read(gi,j); s:=0; q:=2;work; try(1); writeln(min); close(input);close(output); end.,方法2 Program ksd; var a:array150,150 of longint; n,i,j,min:longint; f:array150 of boolean; Procedure go(i,s,sum:longint); var ii:longint; begin if s=n then begin if sum+ai,1=min then exit;,For ii := 1 to n do if fii=false then begin fii:=true; go(ii,s+1,sum+ai,ii); fii:=false; end; end; begin assign(input,salesma.in); assign(output,salesma.out); reset(input); rewrite(output); readln(n); for i := 1 to n do for j := 1 to n do read(ai,j); min:=maxlongint; f1:=true; go(1,1,0); writeln(min); close(input); close(output); end.,例题2、深度优先遍历算法优化 输入n (1=n=2,000,000,000),输出该数据的所有形式不同的因式分解。 样例： 12=12 12=6*2 12=4*3 12=3*4 12=3*2*2 12=2*6 12=2*3*2 12=2*2*3,算法1：减少数据范围或运算次数 利用递归算法： 穷举2N之间的所有整数，若该数是N的约数，则递归对该数进行分解，直到变为1 程序段代码： procedure solve ( n:integer ) ; var i:integer ; begin if n=1 then inc(total) else for i:=2 to n do if n mod i=0 then solve(n div i) end;,算法2： 改进方法：首先将n的所有因子数按从小到大的顺序，存储在一个数组内。 这样在每一层递归时只要穷举当前待分解的数就可以了，由于该数是N的因子，所以它的因子也是N的因子。,Procedure solve(k:longint); var i, j, temp:longint; begin if k=0 then inc(total) else for i:=k downto 1 do if fk mod fi=0 then if fk=fi then inc(total) else begin temp:=fk div fi; j:=k-1; while tempfj do dec(j); solve(j) end end;,begin read(n); s:=0; i:=2; while i*i=n do begin if n mod i=0 then begin inc(s); fs:=i; f-s:=n div i end; i:=i+1 end;,if (i-1)*(i-1)n then j:=-s else j:=-s+1; for i:=j to -1 do begin inc(s); fs:=fi； end; inc(s); fs:=n; total:=0; solve(s); writeln(total); end.,例题3、n个士兵排列问题 有n个士兵（1n26），编号依次为A、B、C， 队列训练时，指挥官要把一些士兵从高到矮依次排成一行。但现在指挥官不能直接获得每个人的身高信息，只能获得“p1比p2高”这样的比较结果（p1，p2A，Z），记为p1p2。 根据这些关系，求出排队方案。 例：AB，BD，FD （没有循环，可以用拓扑排序） 方案：AFBD、FABD、ABFD,拓扑排序应用,Program tppv; n个士兵排队 const maxn=100; var map:array1maxn,1maxn of byte; into:array1maxn of byte; n,i,j,k:byte; Procedure init; var i,j:integer; begin readln(n); fillchar(map,sizeof(map),0); fillchar(into,sizeof(into),0);,while not(seekeof(fp) do begin readln(fp,i,j); mapi,j=1 ; inc(intoj); end; close(fp); end;,begin init; for i:=1 to n do begin j:=1; while (j0) do inc(j); write(j, ); intoj:=255; for k:=1 to n do if mapj,k=1 then dec(intok); end; end.,例题4、雇佣计划： 一个工厂管理员需要确定每个月需要的工人，他知道每个月需要的最少工人数。当他雇佣或解雇一个工人时，需要一些额外支出。一旦一个工人被雇用，即使他不工作，他也将得到工资，同时该管理员知道雇佣一个工人的费用、解雇一个工人的费用和一个工人的工资。他正在考虑为了把项目的费用控制在最低，他将每月雇佣或解雇多少人。 输入：三行，第一行为月数，第二行含有雇佣一个工人费用、一个工人工资、解雇一个工人费用（=100），第三行含n个数，分别表示每个月最少需要的工人数（=1000），每个数据之间有一个空格隔开。 输出：一行，表示项目的最小总费用。,样例： 3 4 5 6 10 9 11 输出 ： 199 问题分析： （1）根据题意需要逐月计算现有工人工作、雇佣工人的雇佣费或解雇工人的费用 （2）确定雇佣方案：当人数不足情况下 设第I个月所需要最少人数为minI大于现有人数now，则需要雇佣工人，其人数minI-now，费用： cost=cost+h*(minI-now), now=minI 雇佣金,Cost=cost+now*s 本月费用总支出 （3）人数多余情况： 当nowminI则需解雇一些人，解雇多少是问题根本： 本例题中，第1个月10人：cost=cost+4*10+5*10=90 第2个月解雇1人 cost=cost+f(now-min2)+d*min2=141 第3个月需11人 cost=cost+h*(min3-now)+d*min3=204 这不是最佳方案，此时可以采取第2个月不解雇的策略： 4*10+5*10+5*10+（4*1+5*11）=199 。 采取贪心策略： 尽可能少的解雇工人，并且在工资支出合理的前提下，尽可能使现有工人数维持在一个最长时间内，以减少雇佣和解雇的额外支出。,实现方法： 在minIminn间按最少需要人数递增的顺序，将月份排列成y1,y2,。 program p3_5 (input,output); Var n,a,b,c,i,j,max,min:integer; s: extended; g: array0100 of integer; begin readln(n); readln(a,b,c);,for i:=1 to n do read(gi); max:=(a+c) div b+1; for i:=1 to n do begin if gi=gi-1 then s:=s+gi*b+(gi-gi-1)*a; if gimin) and (j=n) then min:=gj; if mingi then,begin s:=s+(gi-min)*c; gi:=min; gi+1:=gi; end else begin gi:=gi-1; if gi+1gi then gi+1:=gi; end; s:=s+gi*b; end; end; writeln(s:0:0); end.,例5：Car的旅行路线 ，问题描述： 暑假到了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。,机场 高速铁路 飞机航线 注意：图中并没有 标出所有的铁路与航线。,那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。 找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。输出最小费用，小数点后保留2位。) 输入格式 第一行为一正整数n(0=n=10)，表示有n组测试数据。 每组的第一行有四个正整数s，t，A，B。 S(0S=100)表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，(1=A，B=S)。,接下来有S行，其中第I行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分别是第I个城市中任意三个机场的坐标，Ti为第I个城市高速铁路单位里程的价格。 输出格式： 共有n行，每行一个数据对应测试数据。 样例 输入 1 3 10 1 3 1 1 1 3 3 1 30 2 5 7 4 5 2 1 8 6 8 8 11 6 3 输出： 47.55,分析：简单的几何计算和最短路径相结合的问题 单源最短路径 dijkstra 首先对于每个城市根据给出的三个机场的坐标计算出第四个机场的坐标，以城市A的四个机场分别作为起始结点，以城市B的四个机场分别作为目标结点，用标号法计算出所有最小代值值，从中找出最小代价即为问题的解。,判断垂直的公式（斜率互为负倒数）,Program car; Var n,s,t,a,b,m,u:byte;fn:string; tr:array1100of word; x,y:array1100,14of word; Function dist(c1,p1,c2,p2:byte):extended; Var d1,d2:extended; 两点之间距离 Begin d1:=xc1,p1; d1:=d1-xc2,p2; d2:=yc1,p1; d2:=d2-yc2,p2; dist:=sqrt(sqr(d1)+sqr(d2); End;,Function Dijkstra ( c: byte ):extended; Var use:array1100,14of 01; way: array0100,14 of extended; i, j,mc,mp,lc,lp:byte; Begin fillchar(use,sizeof(use),0); For i:=1 to 4 Do way0,i:=1e38; For i:=1 to s Do For j:=1 to 4 Do wayi,j:=dist(a, c, i, j)*t; For i:=1 to 4 Do usea,i:=1; mc:=0; mp:=1; lc:=0; lp:=1; For i:=1 to s Do For j:=1 to 4 Do If (usei,j=0) And (wayi,jwaymc,mp) Then Begin mc:=i; mp:=j; End; usemc,mp:=1;,While (no