图的最短路径

1图的最短路径2最短路径一、最短路径从一个顶点到另一个顶点最短路径长度，称为最短路径。3从源点Vi到终点Vj的每条路径上的权（它等于该路径上所经边上的权值之和，称为该路径的带权路径长度）可能不同，我们把权值最小的那条路径称为最短路径。例如：图中V1到V5共有三条路径：(v1,v5),(v1,v2,v3,v5),(v1,v2,v4,v5),其带权路径长度分别为30，23和38，其最短路径为23。4二、从一个顶点到其余各顶点的最短路径1、算法的基本思想：广度优先遍历方法。最短路径是指由n个顶点e条边组成的图G，从某个顶点Vi出发，到另一个顶点Vj的最短路径。它可能是直达路径也可能是经过K个点所形成的最短路径。5例题1如图所示6个城市之间道路联系图，编一个程序由计算机找到从C1城市到C6城市之间长度尽可能短的一条路径以及路径总长度。6用广度优先的遍历方法求解最短路径：（1）用邻接矩阵存储图的结构（2）用广度优先的队列存储访问的顶点：（3）记录访问过的城市是一种搜索算法，以便找到最短的路径7顶点123456104800024034603830220404204950624046000940•问题求解的基本方法：广度优先算法（1）存储该图中顶点之间的关系和路径长度（2）从起点开始搜索，将访问点入队，并记录已经被访问过的城市。在搜索中注意本问题中，最先找到的路径未必是最短路径，只是走过城市最少的路径。8•（3）判断当前的路径是否是最短路径•（4）输出最短路径的长度及所访问的过程程序说明如下：programshort;constm=6;max=32767;link:array[1..m,1..m]ofinteger=((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));9typefg=setof1..m;varcity,pnt:array[1..100]ofbyte;flag:array[1..100]offg;flags:fg;i,k,n,r,f:integer;path:array[1..10]of1..m;min,step:integer;procedurework;varn,i,y,cost:integer;s:array[1..10]of1..m;beginy:=f;10n:=0;cost:=0;whiley0dobegininc(n);s[n]:=y;y:=pnt[y];end;fori:=n-1downto1docost:=cost+link[city[s[i+1]],city[s[i]]];ifcostminthenbeginstep:=n-1;min:=cost;fori:=1tostepdopath[i]:=city[s[i]];end;11end;procedureprint;beginwriteln('thesortpath:');write('1');fori:=stepdownto1dowrite('-',path[i]);writeln;writeln('min=',min);end;12beginmin:=max;flag[1]:=[1];city[1]:=1;n:=0;pnt[1]:=0;r:=1;f:=0;repeatinc(f);k:=city[f];ifkmthenbeginflags:=flag[f];forj:=2tomdoif(not(jinflags))and(link[k,j]0)thenbegininc(r);city[r]:=j;flag[r]:=flags+[j];pnt[r]:=f;13iff=mthenwork;end;end;untilf=r；print;readln;end.141Dijktra算法：荻（杰）克斯特拉（1）从源点Vi到其余每个顶点的最短路径的升序依次求出从源点到各顶点最短路径长度。（2）每次求出从源点Vi到一个终点Vj的最短路径后，要以Vj作为新考虑的中间点，用Vi到Vj的最短路径长度和Vi到其它尚未求出最短路径的那些终点的当前最短路径长度进行比较、修改，使它成为当前新的最短路径长度，当进行n-2次后算法结束。15如图所示：（1）设置一个集合数组S，作用是标记已经求得最短路径的终点号，初始值只有一个源点，每找到一个最短路径的终点，将该终点并入S集合中，以便作为新的中间点。若选取为1否则为0（2）设置数组dist，该数组的第j个元素dist[j]用来保存从源点Vi到Vj的目前最短边的路径长度。16（3）设置path为集合数组，存放最短路径经过的顶点集合。对于前面图的结构，假设从V1出发到各个顶点的最短路径，其开始数组S，DIST，PATH的值如下：1000003∞∞30V1V1，V2V1，V5SDISTPATH1234517第一次遍历：123451100003281130V1V1,V2V1,V2,V3V1,V2,V4V1,V5SDISTPATH18第二次遍历：123451101003151123V1V1,V2V1,V2,v4,V3V1,V2,V4V1,v2,V4,v5SDISTPATH19第三次遍历：123451111003151123V1V1,V2V1,V2,v4,V3V1,V2,V4V1,v2,V4,v5SDISTPATH20经过以上遍历，我们得到从V1点到各个顶点的最短路径长度以及最短路径所经过的顶点序号。算法的具体描述：Proceduredijkstra(GA,dist,path,i);{从源点vi点开始}being(1)forj:=1tondo{初始化}beginifjithens[j]:=0elses[j]:=1;dist[j]:=GA[I,j];ifdist[j]maxthenpath[j]:=[i]+[j]elsepath[j]:=[];end;21(2)fork:=1ton-2do{计算到各顶点的最短路径}begin(a)w:=max;m:=I;forj:=1tondo{求出第K个终点Vm}if(s[j]=0)and(dist[j]w)then[m:=j;w:=dist[j]](b)ifmithens[m]:=1elseexit{若条件成立，把Vm并入到S集合中，否则剩余终点路最短径长度均为max}22(c)forj:=1tondo{调整路径}if(s[j]=0)and(dist[m]+GA[m,j]dist[j])thenbegindist[j]:=dist[m]+GA[m,j];path[j]:=path[m]+[j];end;end;{算法的时间复杂性：O（n2）}23三、每对顶点之间的最短路径算法：1、用狄杰斯特拉算法2、floyed算法（弗洛伊德）2425Procedurefloyed(GA,A,P);BEGIN(1)fori:=1tondo{给路径长egin度A和路径P赋初值}forj:=1tondobejinA[I,j]:=GA[I,J];ifA[I,J]maxthenp[I,j]:=[i]+[j]elsep[I,j]:=[]end;26(2)Fork:=1tondofori:=1tondoforj:=1tondobeginif(ik)and(jk)and(ij)thenifA[I,k]+A[k,j]A[I,J]thenbeginA[I,J]:=A[I,K]+A[K,J];P[I,J]:=P[I,K]+P[K,J];end;end;end;27当V1作为中间点，修改最短路径：A[3,2]:=A[3,1]+A[1,2]=4A[3,4]:=A[3,1]+A[1,4]=728当k=2时，V2作为中间点则修改路径长度：原先1到3为max，现在可以根据V2中间点，修改路径长度A[1,3]=A[1,2]+A[2,3]=10A[1,4]=A[1,2]+A[2,4]=3A[3,4]=A[3,2]+A[2,4]=629当K=3时，V3作为中间点，修改与V3相关的路径长度A[2,1]=A[2,3]+A[3,1]=12替换原先的max值。A[4,1]=A[4,3]+A[3,1]=9替换原先的max值。同理可以求出各个顶点的最短路径长度。30四、最短路径的应用31例题1、医院设置：图所示，圈中的数字表示结点中居民的人口，圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和最小，同时约定相邻结点之间的距离为1，如图所示，若医院设在：1处，则距离和=4+12+2*20+2*40=1362处，则距离和=4*2+13+20+40=81………………………………13412204013245输入：第一行一个整数n，表示结点个数接着n行，每行三个数：人口、左连接、右连接（0代表无连接）输出：最小距离和32最短距离和，根据题意对n个结点，共有n个路径之和：S=∑wi*g[I,j](1)求任意两点之间的最短路径(2)求最小的路程和programhospital(input,output);varw:array[1..100]oflongint;g:array[1..100,1..100]oflongint;n,i,j,k,l,r,min,s:longint;33beginreadln(n);fori:=1tondoforj:=1tondog[I,j]:=1000000;fori:=1tondobeging[I,i]:=0;readln(w[i],l,r);ifl0thenbeging[I,l]:=1;g[l,i]:=1；end;34ifr0thenbeging[I,r]:=1;g[r,i]:=1endend;fork:=1tondofori:=1tondoIfikthenforj:=1tondoif(ij)and(kj)and(g[I,k]+g[k,j]g[I,j])theng[I,j]:=g[I,k]+g[k,j];35min:=maxlongint;fori:=1tondobegins:=0;forj:=1tondoinc(s,g[I,j]*w[j]);ifsminthenmin:=send;writeln(min);end.36例题2、产生数（2002年复赛）问题描述给出一个整数n(n1030)和k个变换规则（k=15）。规则：1个数字可以变换成另一个数字规则的右部不能为零。例如：n=234，有规则（k=2）：2→53→637上面的整数234经过变换后可能产生出的整数为（包括原数）：234534264564共4种不同的产生数问题：给出一个整数n和k个规则求出：经过任意次的变换（0次或多次），能产生出多少个不同的整数。仅要求输出个数。38输入：键盘输入，格式为：nkx1y1x2y2…xnyn输出：屏幕输出，格式为：一个整数（满足条件的个数）。样例：输入：输出：23424253639•问题分析：（1）数据的输入：长为30位的数只能以字符串的形式输入，经过转换存入30位的整型数组中。（2）每一位数需要逐个查找和比较、转换，处理时用一个队列q，开始时队列q中只有n。（3）算法流程：front:=1;{队头指针}rear:=1;{队尾指针}whilerear=frontdobeginq出队→y;rear:=rear+1;40根据规则，扩展y，生成新数xi逐个检查xi，如果xi不在队列q中，则xi入队，否则不入队；end;输出front值，即为所求的个数。数据结构：str:string;输入开始的数y,y1:array[1..30]of0..9;工作单元q:array[1..1000,1..30]of0..9;队列，设长度≤1000front,rear:integer;存入和取出指针p:array[1..20,1..2]of0..9;存储变换规则，即p[i,1]→p[i,2]41programc02_3;vari,i0,j,j0,k,front,re