图的最短路径课件

1、1图的最短路径1图的最短路径2最 短 路 径一、最短路径 从一个顶点到另一个顶点最短路径长度，称为最短路径。2最 短 路 径3 从源点Vi到终点Vj的每条路径上的权（它等于该路径上所经边上的权值之和，称为该路径的带权路径长度）可能不同，我们把权值最小的那条路径称为最短路径。 例如：图中V1到V5共有三条路径： (v1,v5),(v1,v2,v3,v5),(v1,v2,v4,v5),其带权路径长度分别为30，23和38，其最短路径为23。3 从源点Vi到终点Vj的每条路径上的权（它等于该路4二、从一个顶点到其余各顶点的最短路径 1、算法的基本思想：广度优先遍历方法。 最短路径是指由n个顶点e条边

2、组成的图G，从某个顶点Vi出发，到另一个顶点Vj的最短路径。它可能是直达路径也可能是经过K个点所形成的最短路径。4二、从一个顶点到其余各顶点的最短路径5例题1 如图所示6个城市之间道路联系图，编一个程序由计算机找到从C1城市到C6城市之间长度尽可能短的一条路径以及路径总长度。5例题1 如图所示6个城市之间道路联系图，编一个程序由计算6用广度优先的遍历方法求解最短路径：（1）用邻接矩阵存储图的结构（2）用广度优先的队列存储访问的顶点：（3）记录访问过的城市是一种搜索算法，以便找到最短的路径6用广度优先的遍历方法求解最短路径：7顶点123456104800024034603830220404204

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

4、2,0), (0,4,2,0,4,9), (0,6,2,4,0,4), (0,0,0,9,4,0); 8（3）判断当前的路径是否是最短路径9type 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 ;

5、 9type fg=set of 1.m ;10 n:=0 ; 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; 11end;12begin min:=max ; flag1:=1 ; city1:=1 ; n:=0 ;pnt1:=0 ; r:=1 ;f:=0; repeat inc(f); k:=cityf; if km th

6、en begin flags:=flagf ; for j:= 2 to m do if (not( j in flags ) and (linkk,j0 ) then begin inc(r); cityr:=j; flagr:=flags+j; pntr:=f ; 12begin13 if f=m then work ; end; end;until f =r ； print ; readln ; end.13 if f=m then work 14Dijktra 算法：荻（杰）克斯特拉 （1） 从源点Vi到其余每个顶点的最短路径的升序依次求出从源点到各顶点最短路径长度。 （2）每次求出从

7、源点Vi到一个终点Vj的最短路径后，要以Vj作为新考虑的中间点，用Vi到Vj的最短路径长度和Vi到其它尚未求出最短路径的那些终点的当前最短路径长度进行比较、修改，使它成为当前新的最短路径长度，当进行n-2次后算法结束。14Dijktra 算法：荻（杰）克斯特拉15如图所示：（1）设置一个集合数组S，作用是标记已经求得最短路径的终点号，初始值只有一个源点，每找到一个最短路径的终点，将该终点并入S集合中，以便作为新的中间点。若选取为1否则为0（2）设置数组dist，该数组的第j个元素distj用来保存从源点Vi到Vj的目前最短边的路径长度。15如图所示：16（3）设置path为集合数组，存放最短路

8、径经过的顶点集合。对于前面图的结构，假设从V1出发到各个顶点的最短路径，其开始数组S，DIST，PATH的值如下： 100000330V1V1，V2V1，V5 S DISTPATH 1 2 3 4 516（3）设置path为集合数组，存放最短路径经过的顶点集合17 第一次遍历： 1 2 3 4 51100003281130V1V1,V2V1,V2,V3V1,V2,V4V1,V5S DISTPATH17 第一次遍历：1100003281130V1V1,V2V18 第二次遍历： 1 2 3 4 51101003151123V1V1,V2V1,V2,v4,V3V1,V2,V4V1,v2,V4,v5S

9、 DISTPATH18 第二次遍历：1101003151123V1V1,V2V19 第三次遍历： 1 2 3 4 51111003151123V1V1,V2V1,V2,v4,V3V1,V2,V4V1,v2,V4,v5S DISTPATH19 第三次遍历：1111003151123V1V1,V2V20经过以上遍历，我们得到从V1点到各个顶点的最短路径长度以及最短路径所经过的顶点序号。算法的具体描述：Procedure dijkstra (GA,dist , path , i) ; 从源点vi点开始 being (1) for j:=1 to n do 初始化 begin if j i then

10、sj:=0 else sj:=1 ; distj:= GAI,j ; if distjmax then path j:= i+j else pathj:= ; end;20经过以上遍历，我们得到从V1点到各个顶点的最短路径长度以21 for k:=1 to n-2 do 计算到各顶点的最短路径 begin (a) w:=max ; m:=I; for j:=1 to n do 求出第K个终点Vm if (sj=0 ) and (distjw) then m:=j; w:=distj (b) if mi then sm:=1 else exit 若条件成立，把Vm并入到S集合中 ，否则剩余终点路

11、最短径长度均为max 21 for k:=1 to n-2 do 22 (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 ） 若要输出所经过的顶点，怎么办？将Path数组定义为字符数组22 (c) for j:=1 to n 23三、每对顶点之间的最短路径算法：1、用狄杰斯特拉算法2、floyed 算法 （ 弗洛伊德）23三、每对顶点之间的最短路径算法：242425Proce

12、dure 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;25Procedure floyed ( GA, A26(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 ( ij) then if AI,k +Ak,j 0 then be

13、gin gI,l := 1; g l,i := 1 ； end; 33begin34if 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 0 then begin35 min := maxlongint; for i := 1 to n do begin s:=0; for j := 1 to n do inc(s, gI,j * wj); if

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

15、整数234经过变换后可能产生出的整数为（包括原数）38输入：键盘输入，格式为：n kx1 y1x2 y2xn yn输出：屏幕输出，格式为：一个整数（满足条件的个数）。样例：输入： 输出：234 2 42 53 638输入：键盘输入，格式为：39问题分析：（1）数据的输入：长为30位的数只能以字符串的形式输入，经过转换存入30位的整型数组中。（2） 每一位数需要逐个查找和比较、转换，处理时用一个队列q，开始时队列q中只有n。（3）算法流程：front:=1;队头指针 rear:=1; 队尾指针while rear=front do begin q出队y; rear:=rear+1; 39问题分析

16、：40 根据规则，扩展y，生成新数xi 逐个检查xi，如果xi不在队列q中，则xi入队， 否则不入队；end; 输出front值，即为所求的个数。 数据结构：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,240 根据规则，扩展y，生成新数xi 41program c02_3; var i,i0,j,j0,k,front,r

17、ear,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); 41program c02_3;42 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 d

18、o 获取变换前的整数 begin q1,j:=ord(stri)-48; 48=ord(0) j:=j+1; end; front:=1; rear:=1;42 readln(k);43while 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

19、:=yj 43while rear=front do44else y1j:=p2; y1为转换后的结果 b:=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; 结束判重 44else 45 if b then begin front:=front+1; 入队列 for j:=1 to 30 do qfront,j:=y1j; end； End； end; end; writeln(

20、front); end. 问题所在：超出数据所规定的范围45 if b then begin46输入：n=11 k=2规则： （1） 1 2 （2） 2 3 宽搜过程：46输入：n=11 k=247队列序号qrear出队情况原始数据转换规则转换后数据入队情况front11111221211122123121212342232112224531233156134121222732231368235222332793323238631123271312238322333992323331033程序结束47队列qrear出队情况原始转换转换后入队情况front148 从本题运行过程中发现，仅11且2

21、个规则就产生了9个不同的数据，如果再增加34，45，89等规则共产生81个不同数(12,13.) ，根据题意n1030，则最多能产生的数据总量9*1029。超出内存空间，益出。 思考：能否用数学递推公式方法 或用dijkstra 最短路径或floyd算法数学公式：数据变换规则数*数据变换规则数， 若数据转换是传递关系则： 11，2（1-2，2-3）则3*3=9 1+2，1+248 从本题运行过程中发现，仅11且2个规则就产生了949如果n是3位数，个位数的可变总数为a1，十位数的可变总数为a2，百位数的可变总数为a3，则共产生a1*a2*a3个不同的数据。用ai表示整数n第i位上的数通过不限次

22、转换可得的数字总个数（包括本身），假定n共有s位，根据乘法原理，n共能转换为a1*a2*a3*as个不同整数。又因为n的各个数位肯定在09之间，可先计算出09分别能转换为多少个不同的数字，分别存储到数组f0f9中，如果n的第i位数值为p，则aI=fp，这样做可以节约不少时间，相信这一点大家不难理解。找到递推关系，用高精度计算方法完成。问题关键在于如何求出递推总数49如果n是3位数，个位数的可变总数为a1，十位数的可变总数50用图来表示这种关系：1、建立一个有向图G，初始化gi, j=False 表示从I到j不存在通路2、如果数字i能直接转换为数字j， 那么gi, j=True3、如何通过有向图

23、，获取fi的值呢？可以用图的遍历方法：深度、宽度 用floyd算法：50用图来表示这种关系：51由于本题的关键在于两结点是否可达，可以采用类似Floyd的有向图的传递闭包算法，该算法实现简单 ，在解决这类问题时比Floyd效率更高。只需将floyd算法中的算术运算符操作+用相应的逻辑运算符and和or代替就可以了，直接在g数组上进行操作，对g数组重新定义为：gi,j=false 表示i到j不可达gi,j=true 表示i可转换为j则有：如果 gi,k=true 且 gk,j=ture ，则 gi,j=true;其算法如下：for k :=0 to 9 dofor i := 0 to 9 do

24、for j := 0 to 9 do gi, j = gi, j or (gi, k and gk, j)51由于本题的关键在于两结点是否可达，可以采用类似Floyd52procedure 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; 52procedure init; 53 j:=n; n:=n-1; while sj= do j:=j+1; val(copy(s,j,2), k, code); fillchar(g , sizeof(g), fals