图的最短路径课件.ppt

1、最最 短短 路路 径径一、最短路径一、最短路径 从一个顶点到另一个顶点最短路径长度，称为最短路从一个顶点到另一个顶点最短路径长度，称为最短路径。径。从源点从源点ViVi到终点到终点VjVj的每条路径上的权（的每条路径上的权（它等于它等于该路径上所经边上的权值之和，称为该路径的带该路径上所经边上的权值之和，称为该路径的带权路径长度）权路径长度）可能不同，我们把权值最小的那条可能不同，我们把权值最小的那条路径称为最短路径。路径称为最短路径。例如：图中例如：图中V1V1到到V5V5共有三条路径：共有三条路径：(v1,v5),(v1,v2,v3,v5),(v1,v2,v4,v5),(v1,v5),(v

2、1,v2,v3,v5),(v1,v2,v4,v5),其带权其带权路径长度分别为路径长度分别为3030，2323和和3838，其最短路径为，其最短路径为2323。二、从一个顶点到其余各顶点的最短路径二、从一个顶点到其余各顶点的最短路径 1、算法的基本思想：广度优先遍历方法。、算法的基本思想：广度优先遍历方法。最短路径是指由最短路径是指由n个顶点个顶点e条边组成的图条边组成的图G，从，从某个顶点某个顶点Vi出发，到另一个顶点出发，到另一个顶点Vj的最短路径。的最短路径。它可能是直达路径也可能是经过它可能是直达路径也可能是经过K个点所形成的个点所形成的最短路径。最短路径。例题例题1 如图所示如图所示

3、6个城市之间道路联系图，编一个程序由个城市之间道路联系图，编一个程序由计算机找到从计算机找到从C1城市到城市到C6城市之间长度尽可能短的一条城市之间长度尽可能短的一条路径以及路径总长度。路径以及路径总长度。用广度优先的遍历方法求解最短路径：用广度优先的遍历方法求解最短路径：（1）用邻接矩阵存储图的结构）用邻接矩阵存储图的结构（2）用广度优先的队列存储访问的顶点：）用广度优先的队列存储访问的顶点：（3）记录访问过的城市）记录访问过的城市是一种搜索算法，以便找到最短的路径是一种搜索算法，以便找到最短的路径问题求解的基本方法：广度优先算法问题求解的基本方法：广度优先算法（1）存储该图中顶点之间的关系

4、和路径长度）存储该图中顶点之间的关系和路径长度（2）从起点开始搜索，将访问点入队，并记录已经被）从起点开始搜索，将访问点入队，并记录已经被访问过的城市。在搜索中注意本问题中，最先找到的路访问过的城市。在搜索中注意本问题中，最先找到的路径未必是最短路径，只是走过城市最少的路径。径未必是最短路径，只是走过城市最少的路径。（3）判断当前的路径是否是最短路径）判断当前的路径是否是最短路径（4）输出最短路径的长度及所访问的过程）输出最短路径的长度及所访问的过程程序说明如下：程序说明如下：program short;const m=6;max=32767;link:array1.m,1.m of inte

5、ger=(0,4,8,0,0,0),(4,0,3,4,6,0),(8,3,0,2,2,0),(0,4,2,0,4,9),(0,6,2,4,0,4),(0,0,0,9,4,0);type fg=set of 1.m;var city,pnt:array1.100 of byte ;flag:array1.100 of fg;flags:fg;i,k,n,r,f:integer;path:array1.10 of 1.m;min,step:integer;procedure work;var n,i,y,cost:integer;s:array1.10 of 1.m;begin y:=f;n:=0

6、;cost:=0 ;while y0 do begin inc(n);sn:=y;y:=pnty;end;for i:=n-1 downto 1 do cost:=cost+linkcitysi+1,citysi;if cost,pathi);writeln;writeln(min=,min);end;begin min:=max;flag1:=1;city1:=1;n:=0;pnt1:=0;r:=1;f:=0;repeat inc(f);k:=cityf;if km then begin flags:=flagf;for j:=2 to m do if (not(j in flags)and

7、(linkk,j0)then begin inc(r);cityr:=j;flagr:=flags+j;pntr:=f;if f=m then work ;end;end;until f=r ；print;readln;end.1 Dijktra 算法：荻（杰）克斯特拉算法：荻（杰）克斯特拉（1）从源点从源点Vi到其余每个顶点的最短路径的升到其余每个顶点的最短路径的升序依次求出从源点到各顶点最短路径长度。序依次求出从源点到各顶点最短路径长度。（2）每次求出从源点）每次求出从源点Vi到一个终点到一个终点Vj的最短路径的最短路径后，要以后，要以Vj作为新考虑的中间点，用作为新考虑的中间点，用Vi到

8、到Vj的最的最短路径长度和短路径长度和Vi到其它尚未求出最短路径的那些到其它尚未求出最短路径的那些终点的当前最短路径长度进行比较、修改，使它终点的当前最短路径长度进行比较、修改，使它成为当前新的最短路径长度，当进行成为当前新的最短路径长度，当进行n-2次后算次后算法结束。法结束。如图所示：如图所示：（1）设置一个集合数组）设置一个集合数组S，作用是标记已经求得最短路，作用是标记已经求得最短路径的终点号，初始值只有一个源点，每找到一个最短路径径的终点号，初始值只有一个源点，每找到一个最短路径的终点，将该终点并入的终点，将该终点并入S集合中，以便作为新的中间点。集合中，以便作为新的中间点。若选取为

9、若选取为1否则为否则为0（2）设置数组）设置数组dist，该数组的第，该数组的第j个元素个元素distj用来保用来保存从源点存从源点Vi到到Vj的目前最短边的路径长度。的目前最短边的路径长度。（3 3）设置）设置pathpath为集合数组，存放最短路径经过的顶点集为集合数组，存放最短路径经过的顶点集合。对于前面图的结构，假设从合。对于前面图的结构，假设从V1V1出发到各个顶点的最短出发到各个顶点的最短路径，其开始数组路径，其开始数组S S，DISTDIST，PATHPATH的值如下：的值如下：100000330V1V1，V2V1，V5 S DISTPATH 1 2 3 4 5 1 2 3 4

10、5 第一次遍历：第一次遍历：1 2 3 4 51100003281130V1V1,V2V1,V2,V3V1,V2,V4V1,V5S DISTPATH 第二次遍历：第二次遍历：1 2 3 4 51101003151123V1V1,V2 V1,V2,v4,V3V1,V2,V4V1,v2,V4,v5S DISTPATH 第三次遍历：第三次遍历：1 2 3 4 51111003151123V1V1,V2V1,V2,v4,V3V1,V2,V4V1,v2,V4,v5S DISTPATH经过以上遍历，我们得到从经过以上遍历，我们得到从V1点到各个顶点的最短路径点到各个顶点的最短路径长度以及最短路径所经过的顶

11、点序号。长度以及最短路径所经过的顶点序号。算法的具体描述：算法的具体描述：Procedure dijkstra(GA,dist,path,i);从源点从源点vi点开始点开始 being (1)for j:=1 to n do 初始化初始化 begin if j i then sj:=0 else sj:=1;distj:=GAI,j ;if distjmax then path j:=i+j else pathj:=;end;(2)for k:=1 to n-2 do 计算到各顶点的最短路径计算到各顶点的最短路径 begin (a)w:=max;m:=I;for j:=1 to n do 求出

12、第求出第K个终点个终点Vm if (sj=0)and (distjw)then m:=j;w:=distj (b)if mi then sm:=1 else exit 若条件成立，把若条件成立，把Vm并入到并入到S集合中集合中，否则，否则剩余终点路最短径长度均为剩余终点路最短径长度均为max (c)for j:=1 to n do 调整路径调整路径 if (sj=0)and (distm+GAm,j distj )then begin distj:=distm+GAm,j ;pathj:=pathm+j;end;end;算法的时间复杂性：算法的时间复杂性：O（n2）三、每对顶点之间的最短路径算

13、法：三、每对顶点之间的最短路径算法：1、用狄杰斯特拉算法、用狄杰斯特拉算法2、floyed 算法算法（弗洛伊德）弗洛伊德）Procedure floyed (GA,A,P);BEGIN (1)for i:=1 to n do 给路径长给路径长egin度度A和路径和路径P赋初值赋初值 for j:=1 to n do bejin A I,j :=GAI,J ;if AI,Jmax then pI,j:=i+j else pI,j:=end;(2)For k:=1 to n do for i:=1 to n do for j:=1 to n do begin if (ik)and (jk)and(

14、ij)then if AI,k+Ak,j 0 then begin gI,l:=1;g l,i:=1；end;if r 0 then begin gI,r:=1;gr,i:=1 end end;for k:=1 to n do for i:=1 to n do If i k then for j:=1 to n do if(i j)and(k j)and(gI,k+gk,j gI,j)then gI,j:=gI,k+gk,j;min:=maxlongint;for i:=1 to n do begin s:=0;for j:=1 to n do inc(s,gI,j*wj);if s min

15、then min:=s end;writeln(min);end.例题例题 2、产生数（产生数（2002年复赛）年复赛）问题描述问题描述给出一个整数给出一个整数n(n1030)和和k个变换规则（个变换规则（k=15）。）。规则：规则：1个数字可以变换成另一个数字个数字可以变换成另一个数字规则的右部不能为零。规则的右部不能为零。例如：例如：n=234，有规则（，有规则（k=2）：）：2 53 6上面的整数上面的整数234经过变换后可能产生出的整数为经过变换后可能产生出的整数为（包括原数）：（包括原数）：234534264564共共4种不同的产生数种不同的产生数 问题：给出一个整数问题：给出一个整

16、数n和和k个规则个规则求出：经过任意次的变换（求出：经过任意次的变换（0次或多次），能产生次或多次），能产生出多少个不同的整数。仅要求输出个数。出多少个不同的整数。仅要求输出个数。输入：键盘输入，格式为：输入：键盘输入，格式为：n kx1 y1x2 y2xn yn输出：屏幕输出，格式为：输出：屏幕输出，格式为：一个整数（满足条件的个数）。一个整数（满足条件的个数）。样例：输入：样例：输入：输出：输出：234 2 42 53 6问题分析：问题分析：（1）数据的输入：）数据的输入：长为长为30位的数只能以字符串位的数只能以字符串的形式输入，经过转换存入的形式输入，经过转换存入30位的整型数组中。位

17、的整型数组中。（2 2）每一位数需要逐个查找和比较、转换，每一位数需要逐个查找和比较、转换，处处理时用一个队列理时用一个队列q，开始时队列，开始时队列q中只有中只有n。（3 3）算法流程：算法流程：front:=1;front:=1;队头指针队头指针 rear:=1;rear:=1;队尾指针队尾指针 while rear=front dowhile rear=front do begin begin q q出队出队y;y;rear:=rear+1;rear:=rear+1;根据规则，扩展根据规则，扩展y y，生成新数，生成新数xi xi 逐个检查逐个检查xixi，如果，如果xixi不在队列不在

18、队列q q中，则中，则xixi入队，入队，否则不入队；否则不入队；end;end;输出输出frontfront值，即为所求的个数。值，即为所求的个数。数据结构：数据结构：str:string;输入开始的数输入开始的数 y,y1:array1.30 of 0.9;工作单元工作单元 q:array1.1000,1.30 of 0.9;队列，设长度队列，设长度1000 front,rear:integer;存入和取出指针存入和取出指针 p:array1.20,1.2 of 0.9;存储变换规则，即存储变换规则，即pi,1pi,2program c02_3;var i,i0,j,j0,k,front,

19、rear,lg,p1,p2:longint;q:array1.1000,1.30 of 0.9;p:array1.20,1.2 of 0.9;y,y1:array1.30 of 0.9;str:string30;b:boolean;begin readln(str);readln(k);for i:=1 to k do readln(pi,1,pi,2);lg:=length(str);for i:=1 to 1000 do for j:=1 to 30 do qi,j:=0;j:=1;for i:=lg downto 1 do 获取变换前的整数获取变换前的整数 begin q1,j:=ord

20、(stri)-48;48=ord(0)j:=j+1;end;front:=1;rear:=1;while rear=front do begin for i:=1 to 30 do yi:=qrear,i;出队列出队列 rear:=rear+1;for i0:=1 to k do begin p1:=pi0,1;p2:=pi0,2;取第取第i0种规则种规则 for j0:=1 to 30 do if p1=yj0 then 可以转换可以转换 begin for j:=1 to 30 do if jj0 then y1j:=yj else y1j:=p2;y1为转换后的结果为转换后的结果 b:=

21、true;i:=1;判断判断y1在队列中是否已存在在队列中是否已存在 while b and (i=front)do begin b:=false;for j:=1 to 30 do if qi,jy1j then b:=true;if b then i:=i+1;end;结束判重结束判重 if b then begin front:=front+1;入队列入队列 for j:=1 to 30 do qfront,j:=y1j;end；End；end;end;writeln(front);end.问题所在：超出数据所规定的范围问题所在：超出数据所规定的范围输入：输入：n=11 k=2规则：规则

22、：（1）1 2 （2）2 3 宽搜过程：宽搜过程：队列队列序号序号qrear出队出队情况情况原始原始数据数据转换转换规则规则转换转换后后数据数据入队入队情况情况front1111 122121112212312 1212342232112224531 233156134121222 732 2313682352223327933 23238 6311232 7131223 83223339 9232333 1033 程序结束程序结束 从本题运行过程中发现，仅从本题运行过程中发现，仅11且且2个规则就产生了个规则就产生了9个不同的数据，如果再增加个不同的数据，如果再增加34，45，89等等规则共

23、产生规则共产生81个不同数个不同数(12,13.)，根据题意，根据题意n1030，则最多能产生的数据总量则最多能产生的数据总量9*1029。超出内存空间，益。超出内存空间，益出。出。思考：能否用数学递推公式方法思考：能否用数学递推公式方法 或用或用dijkstra 最短路径或最短路径或floyd算法算法数学公式：数据变换规则数数学公式：数据变换规则数*数据变换规则数，数据变换规则数，若数据转换是传递关系则：若数据转换是传递关系则：11，2（1-2，2-3）则）则3*3=9 1+2，1+2如果如果n是是3位数，个位数的可变总数为位数，个位数的可变总数为a1，十位数的可变总，十位数的可变总数为数为

24、a2，百位数的可变总数为，百位数的可变总数为a3，则共产生，则共产生a1*a2*a3个不个不同的数据。同的数据。用用ai表示整数表示整数n第第i位上的数通过不限次转换可得的数字总位上的数通过不限次转换可得的数字总个数（包括本身），假定个数（包括本身），假定n共有共有s位，根据乘法原理，位，根据乘法原理，n共共能转换为能转换为a1*a2*a3*as个不同整数。又因为个不同整数。又因为n的各的各个数位肯定在个数位肯定在09之间，可先计算出之间，可先计算出09分别能转换为多少分别能转换为多少个不同的数字，分别存储到数组个不同的数字，分别存储到数组f0f9中，如果中，如果n的第的第i位数值为位数值为p

25、，则，则aI=fp，这样做可以节约不少时间，相，这样做可以节约不少时间，相信这一点大家不难理解。信这一点大家不难理解。找到递推关系，用高精度计算方法完成。找到递推关系，用高精度计算方法完成。问题关键在于如何求出递推总数问题关键在于如何求出递推总数用图来表示这种关系：用图来表示这种关系：1、建立一个有向图、建立一个有向图G，初始化，初始化gi,j=False 表示表示从从I到到j不存在通路不存在通路2、如果数字、如果数字i能直接转换为数字能直接转换为数字j，那么那么gi,j=True3 3、如何通过有向图，获取、如何通过有向图，获取fi的值呢？的值呢？可以用图的遍历方法：深度、宽度可以用图的遍历

26、方法：深度、宽度 用用floyd算法：算法：由于本题的关键在于两结点是否可达，可以采用类似由于本题的关键在于两结点是否可达，可以采用类似Floyd的有向图的传递闭包算法，该算法实现简单的有向图的传递闭包算法，该算法实现简单，在解，在解决这类问题时比决这类问题时比Floyd效率更高。只需将效率更高。只需将floyd算法中的算算法中的算术运算符操作术运算符操作+用相应的逻辑运算符用相应的逻辑运算符and和和or代代替就可以了，直接在替就可以了，直接在g数组上进行操作，对数组上进行操作，对g数组重新定义数组重新定义为：为：gi,j=false 表示表示i到到j不可达不可达gi,j=true 表示表示

27、i可转换为可转换为j则有：如果则有：如果 gi,k=true 且且 gk,j=ture ，则，则 gi,j=true;其算法如下：其算法如下：for k:=0 to 9 dofor i:=0 to 9 do for j:=0 to 9 do gi,j=gi,j or(gi,k and gk,j)procedure init;初始化初始化var code:integer;begin assign(f1,input.txt);reset(f1);readln(f1,s);n:=1;while sn do begin an:=ord(sn)-ord(0);n:=n+1;end;j:=n;n:=n-1

28、;while sj=do j:=j+1;val(copy(s,j,2),k,code);fillchar(g,sizeof(g),false);初始化初始化g、f、b fillchar(f,sizeof(f),0);fillchar(b,sizeof(b),0);for p:=1 to k do 根据输入信息设置根据输入信息设置g数组数组 begin readln(f1,i,j);gi,j:=true;end;for i:=0 to 9 do g i,i:=true;end;procedure floyd;利用利用floyd改进算法，计算改进算法，计算fivar k:integer;begin

29、 for k:=0 to 9 do 通过计算确定通过计算确定i与与j之间的转换关系之间的转换关系 for i:=0 to 9 do for j:=0 to 9 do gi,j:=gi,j or(gi,k and gk,j);for i:=0 to 9 do for j:=0 to 9 do if gi,j then fi:=fi+1;计算计算fi end;K为何作为外循环控制变量为何作为外循环控制变量procedure cheng(x:integer);高精度乘法高精度乘法var k,jw:integer;begin X表示什么表示什么 for j:=1 to 30 do bj:=bj*x;jw:=0;for j:=1 to 30 do begin bj:=bj+jw;jw:=bj div 10;bj:=bj mod 10;end;end;begin init;floyd;b1:=1;for i:=1 to n do cheng(f ai );j:=30;输出最终结果输出最终结果 while bj=0 do j:=j-1;writeln;for i:=j downto 1 do write(bi);end.