数理与信息工程学院.doc

《数理与信息工程学院.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数理与信息工程学院课程论文课程名称图论及其应用题目最短路Dijkstra算法姓名蒋黎锋学号06200104专业信息与计算科学06（1）指导老师卜月华最短路Dijkstra算法1、引言4/4最短路径问题是图论研究的一个重要课题,它广泛应用于交通、网络寻优等领域。最短路径问题要解决的就是求加权图G=中两给定顶点之间的最短路径。求最短路径的一个著名算法是迪克斯特拉(Dijkstra)算法,它可以求出图中从一个顶点到其它各顶点的最短路径的长度及一条最短路径。但是,该算法具有其局限性,它不能求出从一个顶点到其它各顶点的所有

2、最短路径。本文通过对最短路径问题进行深入的分析,提出了Dijkstra的一种改进算法。该算法只需求出从一个顶点到其它各顶点的所有最短路径的长度,不需存储任何最短路径信息即可求出所有最短路径。2、相关概念定义1给定简单加权图,设,,,边,其中是的结点,序列,,称为连接到的路,记为……。路中边的数目称为该路的秩。称为该路的长度。所有连接到的路中长度最小的路称为到的最短路径。定义2给定简单加权图,,称为图的邻接矩阵,其中表示之间边的权值。求最短路径最著名的算法是Dijkstra算法,其基本思想是按路径长度递增的次序产生最短路径,可由

3、下式给出：　　Dijkstra算法具有其局限性,它只能求出一条最短路径,而不能求出所有最短路径。本文提出了Dijkstra的一种改进算法,克服了原算法的不足之处,能够快速地求出一个顶点到其它各顶点的所有最短路径。3、算法与实例为了叙述方便,首先引入以下记号并作相应的约定：(1)A表示图G的邻接矩阵；(2)S表示已找到从出发的最短路径的终点集合；(3)向量D的每个分量D[i]表示从始点到每个终点的最短路径的长度；(4)Succ(u)表示u的后继结点组成的集合。设简单加权图G=(无向图或有向图),则求顶点到其它各顶点

4、的所有最短路径的算法描述如下：(1)初始化S及D。，。4/4(2)选取,使得,令。(3)修改从出发到集合上任一结点可达的最短路径长度。如果D[j]+A[j][k]

5、P[u][w]=D[w]且u≠w}求出每个顶点的后继结点组成的集合；②根据求得的结果按秩的大小输出从源点到其他各顶点的所

6、有最短路径。该算法的时间复杂度与Dijkstra算法相同,为。但是,该算法可以一次求出从一个顶点到其它各顶点的所有最短路径,从而克服了Dijkstra算法的不足之处。下面通过一个例子来说明算法的执行过程。例1　如图1所示,求顶点到其余各顶点的所有最短路径。解：　图1的邻接矩阵为：(1)初始化S及D。，D=(021∞∞)。(2)，令，则。(3)修改从出发到集合上任一结点可达的最短路径长度,D=(0213∞)。(4)。令,则。(5)修改从出发到集合上任一结点可达的最短路径长度,D=(02134)。(6)。令,则。4/4(7)修改从

7、出发到集合上任一结点可达的最短路径长度,D=(02134)。(8)。令,则(9)修改从出发到集合上任一结点可达的最短路径长度,D=(02134)。(10)根据矩阵A和D构造矩阵P如下：根据上面矩阵P、D和公式,求出每个顶点的后继结点组成的集合,则有：，，,于是得到到其它各顶点的所有最短路径，其中秩为1的最短路径为、秩为2的最短路径为、、、，秩为3的最短路径为、、、，秩为4的最短路径为。4、结束语本文针对Dijkstra算法在求最短路径时的局限性,提出了一种求所有最短路径的新算法。该算法可以一次求出从一个顶点到其它各顶点的所有最

8、短路径,因而克服了Dijkstra算法的不足之处。4/4