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