最优化理论与方法 ijsktra算法的实现.doc

最优化理论与方法课程设计 班 级： 信息与计算科学专业1102班 学 号： 1108060214 姓 名： 朱晓东 设计日期： 2013.7.5 西安科技大学计算机学院 摘 要 在实际生活当中，我们需要知道从一个城市到达另一个城市的最短路径，在旅行时可以减少在路途中的时间。路由器的路由表的更新也需要知道两个路由之间的最短距离。很多的关于两点之间的最短路径问题都可以抽象为求最短路径的数学模型。Dijkstra算法和Floyd算法是在求解最短路径问题上的最有效的算法。Dijkstra算法主要应用在求某一顶点到其余各顶点的最短路径。Floyd算法主要应用在求任意一对顶点的最短路径。本论文利用C语言实现了Dijkstra算法和Floyd算法。实际生活中的场景均可抽象成为一个有向图。程序通过实现创建有向图，以有向图作为载体实现对实际问题的求解。 关键字：最短路径，数学模型，Dijkstra算法，Floyd算法，有向图 Dijkstra算法和Floyd算法的实现 算法思想 Dijkstra算法引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条最短路径。此路径为(v,vj)。 那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的权值，或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。Dijstra算法描述如下： 1）arcs表示弧上的权值。若不存在，则置arcs为∞。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcs[Locate Vex(G,v),i] vi∈V 2）选择vj，使得D[j]=Min{D | vi∈V-S} 3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。 Floyd算法是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。采用的是(松弛技术)，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);其状态转移方程如下： shorti][j]=min{short[i][k]+short[k][j],short[i][j]}; 其中short[i][j]表示i到j的最短距离。 流程步骤 Dijkstra算法流程： g为用邻接矩阵表示的带权图；S集合为已找到的从v0出发的最短路径终点集合，他的初始态为{v0}；dist[i]=g.arcs[0][i]. 选择vk，使得dist[k]=min{dist[i]|vi∈V-S}。其中，vk就是当前求得一条从v0出发的最短路径的终点。令S=S∪{vk}。 修改从v0出发到集合V-S上任一顶点vi可达的最短路径长度。如果dist[k]+g.dist[k][i]dist[i],则将dist[i]修改为：dist[k]+g.arcs[k][i]. 重复（2）、（3）步n-1次，即可求得最短路径长度的递增长度的递增顺序，逐个求出v0到图中其他每个顶点的最短路径。 Floyd算法流程： 将vi、vj的最短的路径长度初始化为g.arcs[i][j]，然后进行如何