单源最短路径问题....徐林林4.doc

哈尔滨师范大学
学年论文
题目单源最短路径问题
学生徐林林
指导教师马瑞华讲师
年级 2008级
专业计算机科学与技术
系别计算机科学与技术
学院计算机科学与信息工程
哈尔滨师范大学
2011年 06 月
论文提要
最短路径算法是图论中应用最广的算法之一。许多实际问题只需要简单的数学模型转换,它就成为一个最短路径问题。例如,从城市甲到城市乙,需要经过许多站点和不同路径、怎样选择行走路线,使从甲城市到乙城市所经过的路径最短;如果是乘公交车,那么又有怎样选择乘车方法,使费用最少或时间最短以到达目的地等。这些都是一些典型而又直接的最短路径问题。本文对实际应用中的单源最短路径问题给出了一种贪心解法。文中首先介绍单源最短路径问题,然后对其进行分析和讨论,并证明了该问题具有贪心选择性质和最优子结构性质,并在此基础上给出了该问题的贪心算法。
单源最短路径问题
徐林林
摘要: 本文对实际应用中的单源最短路径问题给出了一种贪心解法。文中首先介绍单源最短路径问题,然后对其进行分析和讨论,并证明了该问题具有贪心选择性质和最优子结构性质,并在此基础上给出了该问题的贪心算法。
关键词:单源最短路径贪心算法
问题描述
所谓单源最短路径问题是指,已知图G=(V,E),我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。如果P是G中从vs到vj的最短路,vi是P中的一个点,那么,从vs沿P到vi的路是从vs到vi的最短路径。
概要设计
对于图G,如果所有Wij≥0的情形下,目前公认的最好的方法是由Dijkstra于1959年提出来的。
已知单行线交通网,数字表示通过这条单行线所需要的费用,现在某人要从v1出发,通过这个交通网到v8去,求使总费用最小的旅行路线。
Dijkstra方法的基本思想是从vs出发,逐步地向外探寻最短路。执行过程中,与每个点对应,记录下一个数(称为这个点的标号),它或者表示从vs 到该点的最短路的权(称为P标号)、或者是从vs到该点的最短路的权的上界(称为T标号),方法的每一步是去修改T标号,并且把某一个具T标号的改变为具 P标号的点,从而使G中具P标号的顶点数多一个,这样至多经过n-1(n为图G的顶点数)步,就可以求出从vs到各点的最短路。
详细设计
在叙述Dijkstra方法的具体步骤之前,说明一下这个方法的基本思想。
s=1,因为所有Wij≥0,故有d(v1, v1)=0。这时,v1是具P标号的点。现在考察从v1发出的三条弧,(v1, v2), (v1, v3)和(v1, v4)。
(1)如果某人从v1出发沿(v1, v2)到达v2,这时需要d(v1, v1)+w12=6单位的费用;
(2)如果他从v1出发沿(v1, v3)到达v3,这时需要d(v1, v1)+w13=3单位的费用;
(3)若沿(v1, v4)到达v4,这时需要d(v1, v1)+w14=1单位的费用。
因为min{ d(v1, v1)+w12,d(v1, v1)+w13,d(v1, v1)+w14}= d(v1, v1)+w14=1,可以断言,从v1到v4所需要的最小费用必定是1单位,即从v1到v4的最短路是(v1, v4),d(v1, v4)=1。这是因为从v1到v4的任一条路P,如果不是(v1, v4),则必是先从v1沿(v1, v2)到达v2,或者沿(v1, v3)到达v3。但如上所说,这时已需要6单位或3单位的费用,不管他如何再从v2或从v3到达v4,所需要的总费用都不会比1小(因为所有wij≥0)。因而推知d(v1, v4)=1,这样就可以使v4变成具P标号的点。
(4)现在考察从v1及v4指向其余点的弧,由上已知,从v1出发,分别沿(v1, v2)、(v1, v3)到达v2, v3,需要的费用分别为6与3,而从v4出发沿(v4, v6)到达v6所需的费用是d(v1, v4)+w46=1+10=11单位。因min{ d(v1, v1)+w12,d(v1, v1)+w13,d(v1, v4)+w46}= d(v1, v1)+w13=3。基于同样的理由可以断言,从v1到v3的最短路是(v1, v3),d(v1, v3)=3。这样又可以使点v3变成具P标号的点,如此重复这个过程,可以求出从v1到任一点的最短路。
在下述的Dijstra方法具体步骤中,用P,T分别表示某个点的P标号、T标号,si表示第i步时,具P标号点的集合。为了在求出从vs到各点的距离的同时,也求出从Vs到各点的最短路,给每个点v以一个λ值,算法终止时λ(v)=m,表示在Vs到v的最短路上,v的前一个点是Vm;如果λ(v)= ∞,表示图G中不含从Vs到v的路;λ(Vs)=0。
Dijstra方法的具体步骤:
{初始化