数理跟信息工程学院.doc

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