《（建筑工程管理）数理与信息工程学院精编.》由会员分享，可在线阅读，更多相关《（建筑工程管理）数理与信息工程学院精编.（5页珍藏版）》请在金锄头文库上搜索。
1、（建筑工程管理）数理与信息工程学院数理和信息工程学院课程论文课程名称 图论及其应用 题目 最短路Dijkstra算法 姓名 蒋黎锋 学号 06200104 专业 信息和计算科学06（1） 指导老师 卜月华 最短路Dijkstra算法1、引言最短路径问题是图论研究的壹个重要课题,它广泛应用于交通、网络寻优等领域。最短路径问题要解决的就是求加权图G=中俩给定顶点之间的最短路径。求最短路径的壹个著名算法是迪克斯特拉(Dijkstra)算法,它能够求出图中从壹个顶点到其它各顶点的最短路径的长度及壹条最短路径。可是,该算法具有其局限性,它不能求出从壹个顶点到其它各顶点的所有最短路径。本文通过对最短路径问
2、题进行深入的分析,提出了Dijkstra的壹种改进算法。该算法只需求出从壹个顶点到其它各顶点的所有最短路径的长度,不需存储任何最短路径信息即可求出所有最短路径。2、相关概念定义1给定简单加权图,设,边,其中是的结点,序列,称为连接到的路,记为。路中边的数目称为该路的秩。称为该路的长度。所有连接到的路中长度最小的路称为到的最短路径。定义2给定简单加权图,称为图的邻接矩阵,其中表示之间边的权值。求最短路径最著名的算法是Dijkstra算法,其基本思想是按路径长度递增的次序产生最短路径,可由下式给出：Dijkstra算法具有其局限性,它只能求出壹条最短路径,而不能求出所有最短路径。本文提出了Dijk
3、stra的壹种改进算法,克服了原算法的不足之处,能够快速地求出壹个顶点到其它各顶点的所有最短路径。3、算法和实例为了叙述方便,首先引入以下记号且作相应的约定：(1)A表示图G的邻接矩阵；(2)S表示已找到从出发的最短路径的终点集合；(3)向量D的每个分量Di表示从始点到每个终点的最短路径的长度；(4)Succ(u)表示u的后继结点组成的集合。设简单加权图G=(无向图或有向图),则求顶点到其它各顶点的所有最短路径的算法描述如下：(1)初始化S及D。，。(2)选取,使得,令。(3)修改从出发到集合上任壹结点可达的最短路径长度。如果Dj+AjkDk,则修改Dk为：Dk=Dj+Ajk。(4)重复操作(
4、2)、(3)共n-1次,求得从到其余各顶点的最短路径长度Dj。(5)按如下方法构造矩阵P：(6)根据矩阵P输出所有最短路径。方法是：按照公式Succ(u)=w|Puw=Dw且uw求出每个顶点的后继结点组成的集合；根据求得的结果按秩的大小输出从源点到其他各顶点的所有最短路径。该算法的时间复杂度和Dijkstra算法相同,为。可是,该算法能够壹次求出从壹个顶点到其它各顶点的所有最短路径,从而克服了Dijkstra算法的不足之处。下面通过壹个例子来说明算法的执行过程。例1如图1所示,求顶点到其余各顶点的所有最短路径。解：图1的邻接矩阵为：(1)初始化S及D。，D=(021)。(2)，令，则。(3)修
5、改从出发到集合上任壹结点可达的最短路径长度,D=(0213)。(4)。令,则。(5)修改从出发到集合上任壹结点可达的最短路径长度,D=(02134)。(6)。令,则。(7)修改从出发到集合上任壹结点可达的最短路径长度,D=(02134)。(8)。令,则(9)修改从出发到集合上任壹结点可达的最短路径长度,D=(02134)。(10)根据矩阵A和D构造矩阵P如下：根据上面矩阵P、D和公式,求出每个顶点的后继结点组成的集合,则有：，,于是得到到其它各顶点的所有最短路径，其中秩为1的最短路径为、秩为2的最短路径为、，秩为3的最短路径为、，秩为4的最短路径为。4、结束语本文针对Dijkstra算法在求最短路径时的局限性,提出了壹种求所有最短路径的新算法。该算法能够壹次求出从壹个顶点到其它各顶点的所有最短路径,因而克服了Dijkstra算法的不足之处。
