资源描述：
《单源最短路径问题徐林林2》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、哈余读师施丸学学年论丈题目单源最短路径问题学生徐林林指导教师马瑞华讲师年级2008级专业计算机科学与技术系别计算机系学院计算机科学与信息工程哈余滨师范大学2011年06月论文提要最短路径算法是图论中应用最广的算法Z—。许多实际问题只需耍简单的数学模型转换，它就成为一个最矩路径问题。例如，从城市甲到城市乙，需耍经过许多站点利不同路径、怎样选择行走路线。使从甲城市到乙城市所经过的路径最短；如果是乘公交车，那么又有怎样选择乘年方法，使费用最少或时间最短以到达H的地等。这些都是一些典型而又直接的最短路径问题。本文对实际应用中的单源最短路径问
2、题给出了一种贪心解法。文中首先介绍单源最短路径问题，然后对其进行分析和讨论，并证明了该问题具有贪心选择性质和最优子结构性质，并在此基础上给出了该问题的贪心算法。请用分页符实现分页！在这个文件中修改之示再发给我！单源最短路径问题徐林林摘要：本文对实际应用中的单源最短路径问题给出了一种贪心解法。文中首先介绍单源最短路径问题，然后对其进行分析和讨论，并证明了该问题具有贪心选择性质和最优子结构性质，并在此基础上给出了该问题的贪心算法。关键词：单源最短路径贪心算法一、问题描述标题应该单独一行。所谓单源最短路径问题是指，已知图G=(V,E),我
3、们希望找出从某给定的源结点SGV到V屮的每个结点的最短路径。我们可以发现有这样一个事实：如果P是G中从vs到vj的最短跖vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最矩路。请不要使用这样口语化的语句。二、概要设计对于图G,如果所有Wij^O的情形下，目前公认的最好的方法是由Dijkstra于1959年提出来的。例1已知如卜•图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用，现在某人要从vl出发，通过这个交通网到去，求使总费用最小的旅行路线。Dijkstra方法的基本思想是从vs出发，逐步地向外探寻最
4、短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为P标号)、或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的改变为具P标号的点，从而使G中具P标号的顶点数多一个，这样至多经过n-1(n为图G的顶点数)步，就可以求出从vs到各点的最短路。三、详细设计在叙述Dijkstra方法的具体步骤之前，以例1为例说明一下这个方法的基本思想。例1中，s二1。因为所有Wij^O,故有d(vl,vl)=0o这时，vl是具P标号的点。现在考察从v
5、l发出的三条弧,(vl,v2),(vl,v3)和(vl,v4)o如果某人从vl出发沿(vl,v2)到达v2,这时需要d(vl,vl)+wl2=6单位的费用;如果他从vl出发沿(vl,v3)到达v3,这时需要d(vl,vl)+wl3=3单位的费用；类似地，若沿(vl,v4)到达v4,这时需要d(vl,vl)+wl4=l单位的费用。因为min{d(vl,vl)+wl2,d(vl,vl)+wl3,d(vl,vl)+wl4}=d(vl,vl)+wl4=l,可以断言，他从vl到v4所需要的最小费用必定是1单位，即从vl到v4的最短路是(vl,
6、v4),d(vl,v4)=lo这是因为从vl到v4的任一条路P,如果不是(vl,v4),则必是先从vl沿(vl,v2)到达v2,或者沿(vl,v3)到达v3。但如上所说,这时他已需要6单位或3单位的费用,不管他如何再从边或从v3到达v4,所需耍的总费用都不会比1小(因为所有wijNO)。因而推知d(vl,v4)二1,这样就可以使v4变成具P标号的点。现在考察从vl及v4指向其余点的弧，由上已知,从vl出发,分别沿(vl,v2)、(vl,v3)到达v2,v3,需要的费用分别为6与3,而从v4出发沿(v4,v6)到达v6所需的费用是d(
7、vl,v4)+w46=l+10=l1单位。因min{d(vl,vl)+wl2,d(vl,v1)+w13,d(vl,v4)+w46}=d(vl,vl)+wl3二3。基于同样的理由可以断言，从vl到v3的最短路是(vl,v3),d(vl,v3)二3。这样又可以使点变成具P标号的点，如此重复这个过程，可以求出从vl到任一点的最短路。在下述的Dijstra方法具体步骤中，用P,T分别表示某个点的P标号、T标号，si表示第i步时，具P标号点的集合。为了在求出从VS到各点的距离的同时，也求出从Vs到各点的最短路，给每个点v以一个入值，算法终止时
8、X(v)=m,表示在Vs到v的最短路上,v的前一个点是Vm；如果入(v)二8,表示图G中不含从Vs到v的路；X(Vs)=0oDijstra方法的具体步骤：｛初始化｝i二0SO二｛Vs｝,P(Vs)二0X(Vs)=0对每一个vOVs,令
