单源最短路径问题徐林林1

1、哈尔滨师范大学学年论文题 目 单源最短路径问题学 生 徐林林指导教师 马瑞华 讲师年 级 2008级专 业 计算机科学与技术系 别 计算机科学与技术学 院 计算机科学与信息工程哈尔滨师范大学2011年06月论 文 提 要最短路径算法是图论中应用最广的算法之一。许多实际问题只需要简单的数学模型转换，它就成为一个最短路径问题。例如，从城市甲到城市乙，需要经过许多站点和不同路径、怎样选择行走路线，使从甲城市到乙城市所经过的路径最短；如果是乘公交车，那么又有怎样选择乘车方法，使费用最少或时间最短以到达目的地等。这些都是一些典型而又直接的最短路径问题。本文对实际应用中的单源最短路径问题给出了一种贪心解法

2、。文中首先介绍单源最短路径问题，然后对其进行分析和讨论，并证明了该问题具有贪心选择性质和最优子结构性质，并在此基础上给出了该问题的贪心算法。单源最短路径问题徐林林摘 要: 本文对实际应用中的单源最短路径问题给出了一种贪心解法。文中首先介绍单源最短路径问题，然后对其进行分析和讨论，并证明了该问题具有贪心选择性质和最优子结构性质，并在此基础上给出了该问题的贪心算法。关键词：单源最短路径 贪心算法 一、 问题描述 所谓单源最短路径问题是指，已知图G（V，E），我们希望找出从某给定的源结点SV到V中的每个结点的最短路径。如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是

3、从vs到vi的最短路径。二、 概要设计对于图G，如果所有Wij0的情形下，目前公认的最好的方法是由Dijkstra于1959年提出来的。已知单行线交通网，数字表示通过这条单行线所需要的费用，现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。Dijkstra方法的基本思想是从vs出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs 到该点的最短路的权(称为P标号)、或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的改变为具 P标号的点，从而使G中具P标号的顶点数多一个，这

4、样至多经过n-1(n为图G的顶点数)步，就可以求出从vs到各点的最短路。三、 详细设计在叙述Dijkstra方法的具体步骤之前，说明一下这个方法的基本思想。s=1，因为所有Wij0，故有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单位

5、的费用。因为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小(因为所有wij0)。因而推知d(v1, v4)=1，这样就可以使v4变成具P标号的点。（4）现在考察从

6、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标号、

7、T标号，si表示第i步时，具P标号点的集合。为了在求出从vs到各点的距离的同时，也求出从Vs到各点的最短路，给每个点v以一个值，算法终止时(v)=m，表示在Vs到v的最短路上，v的前一个点是Vm；如果(v)= ，表示图G中不含从Vs到v的路；(Vs)=0。Dijstra方法的具体步骤：初始化i=0S0=Vs，P(Vs)=0 (Vs)=0对每一个v<>Vs，令T(v)=+ ，(v)=+ ，k=s开始如果Si=V，算法终止，这时，每个vSi，d(Vs,v)=P(v)；否则转入考察每个使(Vk,vj)E且vj Si的点vj。如果T(vj)>P(vk)+wkj，则把T(vj)修改为P

8、(vk)+wkj，把(vj)修改为k。如果T(vj)<P(vk)+wkj，则把T(vj)的标号变为P标号，令k=ji，i=i+1，转，否则终止，这时对每一个vSi，d(vs,v)=P(v)，而对每一个查询。四、 实现程序:/ Graph.h#pragma once#define maxPoint 100class CGraphpublic:CGraph(void);CGraph(void);bool SetGraph( double gmaxPointmaxPoint , int startPoint , int size );bool Dijkstra();void Display()

9、;int GetStartPoint();double GetBestWay( int dest , int path , int &pathLen );private:/标志当前图是否已经求解bool solved;/当前图布局double graphmaxPointmaxPoint;/地图大小int size;/起点int startPoint;/当前图的解double distmaxPoint;int prevmaxPoint;/ Graph.cpp#include "StdAfx.h"#include ".graph.h"CGraph:C

10、Graph(void)for( int i = 0 ; i < maxPoint ; i+ ) for( int j = 0 ; j < maxPoint ; j+ ) graphij = -1;startPoint = -1;size = -1;/当前图还没有求解solved = false;CGraph:CGraph(void)/bool CGraph:SetGraph( double gmaxPointmaxPoint , int startPoint , int size )for( int i = 0 ; i < size ; i+ ) for( int j = 0

11、 ; j < size ; j+ ) graphij = gij;this->startPoint = startPoint;this->size = size;solved = false;Dijkstra();return true;/bool CGraph:Dijkstra()bool smaxPoint;for( int j = 0 ; j < size ; j+ ) distj = graphstartPointj; sj = false; /disti<0，表示没有路径连接结点startPoint 与结点j if( distj < 0 ) pre

12、vj = 0; else prevj = startPoint;/从起点出发diststartPoint = 0;sstartPoint = true;for( int i = 0 ; i < size ; i+ ) double temp; int u = startPoint; bool flag = false; for( int j = 0 ; j < size ; j+ ) if( !sj ) /如果不是第一次比较，temp u，都已经赋值，则 if( flag ) if( distj > 0 && distj < temp ) u = j;

13、temp = distj; else u = j; temp = distj; flag = true; su = true; for( int j = 0 ; j < size ; j+ ) if( !sj && graphuj > 0 ) double newDist = distu + graphuj; if( distj < 0 | newDist < distj ) distj = newDist; prevj = u; /标记当前问题已经解决solved = true;return true;/void CGraph:Display()pri

14、ntf( "当前地图的邻接矩阵n" );for( int i = 0 ; i < size ; i+ ) for( int j = 0 ; j < size ; j+ ) printf( "%5.f" , graphij ); printf( "n" );/double CGraph:GetBestWay( int dest , int path , int &pathLen )int p = dest;int thewaymaxPoint;int len = 0;while( p != startPoint )

15、thewaylen = p; p = prevp; len+;thewaylen = startPoint;len+;for( int i = 0 , j = len - 1 ; i < len ; i+ , j- ) pathi = thewayj;pathLen = len;return distdest;/int CGraph:GetStartPoint()return startPoint;/ Dijkstra.cpp : 定义控制台应用程序的入口点。/#include "stdafx.h"#include "conio.h"#includ

16、e "Graph.h"int main(int argc, char * argv)double graphmaxPoint = 0 , 50 , 10 , 0 , 45 , 0 , 0 ， 0 ，15 ，0 ，10 ，0 , 20 ，0 ，0 ，15 ，0 ，0 , 0 ，20 ，0 ，0 ，35 ，0 , 0 ，0 ，0 ，30 ，0 ，5 0 ，0 ，0 ，3 ，0 ，0 ;int size = 6;int start = 0;int dest = 1;int pathlen;int pathmaxPoint;double dist;CGraph g;g.SetGra

17、ph( graph , start , size );g.Display();printf( "-n" );for( dest = 0 ; dest < size ; dest+ ) dist = g.GetBestWay( dest , path , pathlen ); printf( "从 %d 到 %d 的最短路径长 %.fn" , g.GetStartPoint() , dest , dist ); printf( "所经结点为:n" ); for( int i = 0 ; i < pathlen ; i+ )

18、printf( "%3d" , pathi ); printf( "n-n" );getch();return 0;/五、算法分析和改进： 贪心算法是一种重要的算法设计策略，它与动态规划算法的设计思想有一定的联系，但其效率更高。贪心算法，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。通过上面程序显示结果，能够得到其最短路径。本问题的时间复杂度为O（n2）。六、总结：本文通过单源最短路径问题出发，用贪心算法解决该问题。深刻了解了贪心算法的最优子结构性质和贪心选择性质，虽然过程中出现很多问题，但通过老师的指导让我很快了解问题出现在哪里并将其改正。通过本次学年论文也使我学习到很人生的道理，要正式面对所遇到的问题和困难，不退缩，不放弃，做事还一定要细心谨慎，一切按照要求看来做，最终一定会得到一个满意的结果。七、参考文献：【1】王晓东 ：计算机算法设计与分析（第三版），电子工业出版社。【2