数理与信息工程学院

数理与信息工程学院课程论文课程名称图论及其应用题目最短路Dijkstra算法姓名蒋黎锋学号06200104专业信息与计算科学06（1）指导老师卜月华最短路Dijkstra算法1、引言最短路径问题是图论研究的一个重要课题,它广泛应用于交通、网络寻优等领域。最短路径问题要解决的就是求加权图G=V,E,W中两给定顶点之间的最短路径。求最短路径的一个著名算法是迪克斯特拉(Dijkstra)算法,它可以求出图中从一个顶点到其它各顶点的最短路径的长度及一条最短路径。但是,该算法具有其局限性,它不能求出从一个顶点到其它各顶点的所有最短路径。本文通过对最短路径问题进行深入的分析,提出了Dijkstra的一种改进算法。该算法只需求出从一个顶点到其它各顶点的所有最短路径的长度,不需存储任何最短路径信息即可求出所有最短路径。2、相关概念定义1给定简单加权图,,GVEW,设0v,1v,,mvV,边12,,,meeeE,其中1,iivv是ie的结点,序列0v,1v,,mv称为连接0v到mv的路,记为0v1v……mv。路中边的数目称为该路的秩。0112(1)nn称为该路的长度。所有连接0v到mv的路中长度最小的路称为0v到mv的最短路径。定义2给定简单加权图,,GVEW,011{,,}nVvvv,称()ijAa为图G的邻接矩阵,其中ij表示ijvv和之间边的权值。求最短路径最著名的算法是Dijkstra算法,其基本思想是按路径长度递增的次序产生最短路径,可由下式给出：[]min{[],[]}jiDiDiDiDijkstra算法具有其局限性,它只能求出一条最短路径,而不能求出所有最短路径。本文提出了Dijkstra的一种改进算法,克服了原算法的不足之处,能够快速地求出一个顶点到其它各顶点的所有最短路径。3、算法与实例为了叙述方便,首先引入以下记号并作相应的约定：(1)A表示图G的邻接矩阵；(2)S表示已找到从0v出发的最短路径的终点集合；(3)向量D的每个分量D[i]表示从始点0v到每个终点iv的最短路径的长度；(4)Succ(u)表示u的后继结点组成的集合。设简单加权图G=V,E,W(无向图或有向图),011{,,}nVvvv则求顶点0v到其它各顶点的所有最短路径的算法描述如下：(1)初始化S及D。0{}Sv，[][0,],0,1,,1DiAiin。(2)选取jv,使得[]min{[]/}iDjDivVS,令{}jSSv。(3)修改从0v出发到集合VS上任一结点kv可达的最短路径长度。如果D[j]+A[j][k]D[k],则修改D[k]为：D[k]=D[j]+A[j][k]。(4)重复操作(2)、(3)共n-1次,求得从0v到其余各顶点jv的最短路径长度D[j]。(5)按如下方法构造矩阵P：(6)根据矩阵P输出所有最短路径。方法是：①按照公式Succ(u)={w|P[u][w]=D[w]且u≠w}求出每个顶点的后继结点组成的集合；②根据求得的结果按秩的大小输出从源点到其他各顶点的所有最短路径。该算法的时间复杂度与Dijkstra算法相同,为2()On。但是,该算法可以一次求出从一个顶点到其它各顶点的所有最短路径,从而克服了Dijkstra算法的不足之处。下面通过一个例子来说明算法的执行过程。例1如图1所示,求顶点0v到其余各顶点的所有最短路径。解：图1的邻接矩阵为：(1)初始化S及D。0{}Sv，D=(021∞∞)。(2)[2]min{[]/}1iDDivVS，令2{}SSv，则02{,}Svv。(3)修改从0v出发到集合VS上任一结点kv可达的最短路径长度,D=(0213∞)。(4)[1]min{[]/}2iDDivVS。令1{}SSv,则012{,,}Svvv。(5)修改从0v出发到集合VS上任一结点kv可达的最短路径长度,D=(02134)。(6)[3]min{[]/}3iDDivVS。令3{}SSv,则0134{,,,}Svvvv。(7)修改从0v出发到集合VS上任一结点kv可达的最短路径长度,D=(02134)。(8)[4]min{[]/}4iDDivVS。令4{}SSv,则01234{,,,,}Svvvvv(9)修改从0v出发到集合VS上任一结点kv可达的最短路径长度,D=(02134)。(10)根据矩阵A和D构造矩阵P如下：根据上面矩阵P、D和公式(){/[][][]}SuccuwPuwDwuw且,求出每个顶点的后继结点组成的集合,则有：012(){,}Succvvv，134(){,}Succvvv，213(){,}Succvvv34(){}Succvv,4()Succv于是得到0v到其它各顶点的所有最短路径，其中秩为1的最短路径为01vv、12vv秩为2的最短路径为013vvv、014vvv、021vvv、023vvv，秩为3的最短路径为0134vvvv、0213vvvv、0214vvvv、0234vvvv，秩为4的最短路径为02134vvvvv。4、结束语本文针对Dijkstra算法在求最短路径时的局限性,提出了一种求所有最短路径的新算法。该算法可以一次求出从一个顶点到其它各顶点的所有最短路径,因而克服了Dijkstra算法的不足之处。