邻接矩阵求带权图中最短通路-论文.pdf

《邻接矩阵求带权图中最短通路-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2013年l1月NOM．2013安庆师范学院学报(自然科学版)第19卷第4期V0I．19N0．4JournalofAnqingTeachersCollege(NaturalScienceEdition)网络出版时间：2013—12—1920：16网络出版地址：http：／／www．cnki．net／kcms／detail／34．1150．N．20131219．2016．008．html邻接矩阵求带权图中最短通路黄师化(安庆师范学院计算机与信息学院，安徽安庆246133)摘要：通过对带权邻接矩阵定义一种运算，计算n阶简单带权图中任意两点之间步长为l，2，⋯，n—l的最短通路长度，逐步比较，确

2、定通路所过各边权值之和最小的即最短路径。在汁算的过程中用矩阵记下最短路径所经过的所有结点，最后验证了其在无向和有向简单带权图中的有效性。关键词：带权邻接矩阵；带权图；最短通路；矩阵算法中图分类号：0157．5文献标识码：A文章编号：1007—4260(2013)04—0026—03设G=(V，E，W)是一个n阶简单带权图⋯，出长度最短的通路。其中每条边标有权值。定义其带权邻接矩阵A=具体算法：构造G的邻接矩阵A，从A出发构(n，)⋯l2J，其中n为顶点和f之问的边对应造出1l,一1个n阶方阵，A，，⋯，A。其中A=的权值，若G是有向图，则a，，为顶点邻接到，(。)⋯，f=2，3，4，⋯，n

3、一1。0表示与vj之边对应的权值，若这样的边不存在，则记a．=∞。间所有步长≤Z的最短通路的长度。为了便于求可见无向图的带权邻接矩阵一定是对称的，而有最短通路时进行回溯，构造出一个矩阵D=向图则不一定。两个顶点之间可能有多条通路，称(di，)⋯，其中d，表示顶点到f之间最短通路通路经过的边的权值之和为通路的长度⋯，两点的步长。A的构造过程分为两步：间所有通路中长度最短的称之为距离¨J。通路所第一步：初步计算4，A=A·+A=经过的边的条数称为通路的步长J。(Ⅱ：)，z=2，3，4，⋯，n一1。1带权邻接矩阵的“点加”运算及几何意义第二步：比较A与A，．．，改造A，方法如下：若与之问存在步长

4、≤z的通路或步长≤z一定义带权邻接矩阵A之间的运算，记做·+，1的通路，即min{0，}<。。，如果alfI<记A：=A·+A=(0)，其中n=rain{Ⅱ’n，则d，=f，否则d=f—I。重新计算A，其+rzlk=1，2，⋯，n}，可见，口为顶点和，之，中n=min，。”}。间的步长为2的最短通路的长度，对应的k为中问经过的节点编号。以此类推，A，=A·+A=观察最后求得的A。，其中元素rz代表的(n，其中n=rain+。，Ik=1，2，就是顶点．-q，之间距离。主对角线元素全0，代⋯表顶点到自身距离为0，其他处为∞则代表对应，n}，可见，n：为顶点和之问的步长为z的两点不连通，可以理解

5、距离为无穷大。最后求得的最短通路的长度，对应的k为前一节点编号。矩阵D，其中元素d，代表的就是顶点与之问2两点间最短通路及距离的求解算法最短通路的步长。带权邻接矩阵求两个不同点之间距离的思想邻接矩阵求两个不同点间最短通路的思想是：在两点问步长为1，2，，3⋯，凡一l的通路中找是：在构造A=(0)⋯，z=2，3，4，⋯，n一1的收稿日期：20l3—05—29作者简介：黄师化，女，安徽太湖人，安庆师范学院计算机信息学院讲师，研究方向：智能计算。第4期黄9币化：邻接矩阵求带权图中最短通路·27·同时，构造出通路矩阵path=()xn'z=2，3，b[i][i]=0；4，⋯，n一1，其中元素表示顶

6、点到之间步长为Z的最短通路中的前一顶点编号。／／求起点到其他各点的最短通路当口：≠∞时，p=Ii}(后=l，2，⋯，n)，后为p[0]=start；for(j=0；j=1)到之间最短通路步长为

7、i}，则从秒开始回溯至前{P[step]=e_d；-NA『

8、=p，继续回溯至『l的前一顶点：e_d=path[step儿start][e_d]；p(k-“继续此过程直至

9、起点，记下所经过顶点，step一一；}编号，即为顶点到之间的最短通路。printf(”V％d⋯>V％d的距离为：％d，通路为：”，start，j，b[start][j])；3程序代码(无向图)printf(”％d”，p[0])；／／构造A2，A3，⋯⋯，A及通路矩阵pathfor(k=1；k<=d[start][j]；k++)for(ent=2；ent％d”，P[k])；{for(i