基于DIJKSTRA算法的路由选择

摘要通过对《图论及其算法》深入的学习，本文简单介绍了图论的发展与特点，阐述了最短路径问题及其算法。并采用迪克斯屈拉算法解决最短路由问题。众所周知，图论是数学的一个分支，它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这些图形通常用来描述某些事物之间的特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有的关系。最短路由的问题利用了图的描述，并把算法用C++语言来实现，这就很好地将所学知识和现实生活结合起来。关键词：最短路径Dijkstra算法C++AbstractBasedonthegraphtheoryandalgorithmofin-depthstudy,thispaperbrieflyintroducesthedevelopmentandcharacteristicsofgraphtheory,presentstheshortestpathproblemanditsalgorithm,andadoptsDijkstraalgorithmtosolvetheshortestroutingproblem.Asisknowntoall,graphtheoryisabranchofmathematics,itsoastheresearchobject.Graphtheoryinthediagramconsistsinsomegivenpointsandthelinesconnectingtwopointsofagraph,thesegraphicsareusuallyusedtodescribethespecificrelationshipbetweenthings,usingpointsrepresentativethings,usingthelinesconnectingtwopointsrepresentativethecorrespondingrelationshipbetweenthings.Theshortestroutingproblemmakesuseofgraphdescription,andtherealizationofthealgorithm,whichtakesadvantageofC++.itisagoodwaytocombinetheknowledgewe’velearnedwithourlife.Keyword:shortestpathDijkstra'salgorithmC++引言随着现代通信技术的不断发展，通信网的范围也逐渐扩大，通信网已成为人们生活中不可或缺的一部分了。而随着人们之间通信次数的增加，使的通信网的通信量也随之大量增加。这给通信网带了沉重的负担。如何在现有通信网的基础上提高通信效率，网络利用率和网络可靠性[1]，以满足人们日益增长的对网络通信能力的需求已成为对通信网研究的主要内容。迪克斯屈拉算法是最适合解决网络拓扑中两节点间的最短通信距离的问题的方法之一。本文就如何利用迪克斯屈拉算法解决网络中点到点通信的最短距离问题做了说明，以此提高通信网的通信效率。第一章迪克斯屈拉算法1.1算法介绍Dijkstra(迪克斯屈拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边[3]。ProcedureDijkstra（G：所有权都为正数的加权连通简单图）{G带有定点a=v0,v1……，vn=z和权w（vi,vj）,若{vi,vj}不是G中的边，则w（vi,vj）=∞}Fori:=1tonL（vi）:=∞L（a）:=0S:=φ{初始化标记，a的标记为0，其余结点标记为∞，S是空集}WhilezSbeginu:=不属于S的L（u）最小的一个顶点S：=S{u}for所有不属于S的顶点vifL(u)+w(u,v)L(v)thenL(v):=L(u)+w(u,v){这样就给S中添加带最小标记的顶点并且更新不在S中的顶点标记}end{L（z）=从a到z的最短路的长度}1.2根据Dijkstra算法给出的定理定理1迪克斯屈拉算法求出连通简单无向加权图中的两个顶点之间最短路的长度[2]。迪克斯屈拉算法通过一步一步的迭代求出最短路径，假设在第k次迭代中。在s中的顶点v的标记L(v)是从a到这个顶点v的最短路的长度。不在s中的顶点的标记是（除了这个顶点自身之外）只经过s中顶点的从a到这个顶点的最短路的长度。设u是第k次迭代结束时带最小标记的不在s中的顶点（若该顶点不唯一，可采用带最小标记的任意顶点）。在第k+1次迭代中，u是添加到s中的顶点，则在第k+1次迭代中，u的标记必须是a到u的最短路的长度。否则，k次迭代后，从结点a到某个结点l的路，其路得长度小于Lk（v）。定理2迪克斯屈拉算法使用O（n2）次运算（加法和比较）来求出n阶连通简单无向加权图中两个顶点之间最短路的长度,求加权无向图中最短路的Dijkstra算法可以推广到求加权有向图中最短有向路。定理3设有向图G中不含长度非正的有向圈，并且从点1到其余各点都有有限长的有向路,那么G中结点1到其余各点j的最短有向路长度Sj有唯一有限解{Sj}。定理4设Sj是加权有向图G中自结点1到结点j的最短有向路的长度，并且对所有的j=1，2，3，……，n，Sj为有限值。若图G中除结点1外的其余各点能重新编写成如下的序号2，3，……，n使得对所有ij，成立Si≤Sj且wj,i≥0或者SiSj且wj,i=,即j,iE（G），则定理5设G=V,E是一个边权为正值的有向图，其中V={1，2，3……，n}。则在G中，任意一条最短有向路得长都大于它的真子有向路的长。Dijkstra算法求出了图中一个特定顶点到其他各定点的最短路，可以利用Dijkstra算法解决实际生活中的一些问题。第二章Dijkstra算法的实际应用2.1问题的提出在现实生活中，我们常常会遇到很多问题，都是要找到一个地方到另一个地方的最短路径，当然还要满足各方面的要求，包括可实现性、预算、带来的利益等各方面条件[4]。比如Dijkstra算法在计算机网络路由问题中的应用。通常我们解决的办法就是找到一条距离最短，又在现实可接受范围内的路径。2.2运用Dijkstra算法解决实际问题在通信网中，如何利用现有的通信网络，通过最短的通信路径完成信息的传递，在通信网研究中具有重要意义。为了降低研究复杂性，我们假设每条通信线路的通信系能和状况都一样且恒定不变。建立如下网络模型：点用来表示路由节点（用a到e及z…表示），边用来表示两节点间的通信线路，边上的权重表示两节点间的距离，节点本身到他自己的距离记为0，如果两节点没有边直接相连用∞表示。利用Dijkstra算法实现求解最短路径问题要有边权。本文最佳路径是基于两个路由节点间的距离。因此找路由节点间的最短距离就转化成了找图G=（V,E）中指定两点间的最小距离了。首先我们利用上图可以知道节点之间的邻接关系，为此我们可以先画出节点间的邻接矩阵，方便我们对节点的关系进行了解。如下表（单位：m）：abcdeza0400200∞∞∞b4000100500∞∞c20010008001000∞d∞5008000200600e∞∞10002000300z∞∞∞6003000下面对最优路径进行分析，我们a为路径的起点，z为终点。初始化：L(a)=0L(b)=∞，L(c)=∞，L(d)=∞，L(e)=∞，L(z)=∞，S=Φ,一次迭代：U=a，S={a}L(a)+W(a,b)=0+400=400L(b)L(a)+W(a,c)=0+200=200L(c)L(a)+W(a,d)=0+∞=∞L(a)+W(a,e)=0+∞=∞L(a)+W(a,z)=0+∞=∞L(b)=400,L(c)=200,L(d)=L(e)=L(z)=∞二次迭代：U=c，S={a,c}L(c)+W(c,b)=200+100=300L(b)L(c)+W(c,d)=200+800=1000L(d)L(c)+W(c,e)=200+1000=1200L(e)L(c)+W(c,z)=200+∞=∞L(b)=300，L(d)=1000，L(e)=1200，L(z)=∞三次迭代：U=b，S={a，c，b}L(b)+W(b,d)=300+500=800L(d)L(b)+W(b,e)=300+∞=∞∞L(b)+W(b,z)=300+∞=∞L(d)=800，L(e)=1200,L(z)=∞四次迭代：U=d，S={a，c，b，d}L(d)+W(d,e)=800+200=1000L(e)L(d)+W(d,z)=800+600=1400L(z)L(e)=1000，L(z)=1400五次迭代：U=e，S={a，c，b，d，e}L(e)+W(e,z)=1000+300=1300L(z)L(z)=1300结束：U=z，S={a，c，b，d，e，z}由于终点z已经进入S集合中所以迭代结束。这样就找到了从起点a到终点z的最短路径以及到中间各点的最短路径。本文的算法是在VC++的环境下实现的，程序的基本思想是基于Dijkstra算法的。这个程序中是以节点1代表a，且以节点1作为初始节点，节点6最为终止节点，在程序中所求的最短路径问题则为从节点1到节点6以及其他中间节点的最短路径[5]。具体的程序代码见附录。图2运行结果第三章结论通过本学期对《图论及其算法》的学习，使我深刻体会到了图论在实际生活中的广泛应用，也使从以前的定向思维上升了一个台阶，学会把抽象的变为具体，能用点、线、图来描述抽象的事物，把很多抽象的知识具体化，使得抽象的知识更容易理解、记忆。《图论及其算法》中有很多简便的算法，可以实现很多功能。Dijkstra算法是图论众多算法中的一种，能够方便的找到两点之间的最短路径，通过上面Dijkstra算法的应用例子可以清楚的看到通过Dijkstra算法可以在很复杂的图中很容易的找到点到点的最短路径，也可以对实际生活中的一些问题给予很大的帮助。参考文献[1]乐阳,龚健雅;Dijkstra最短路径算法的一种高效率实现[J];武汉测绘科技大学学报;1999年03期.[2]殷剑宏，吴开亚；《图论及其算法》，中国科学技术大学出版社；2005.[3]王树禾.图论[M].北京：科学出版社.2009.[4]凡金伟,吕康.基于Dijkstra算法在物流配送中的应用[J].电脑编程技巧与维护,2009,(04).[5]徐凤生，李天志.所有最短路径的求解算法[J].微计算机应用，2004，25（3）：295-300.附录#includeiostream.h#includestdio.h#defineMaxNum10000//节点间不是邻居节点#definen6//节点数目intdist[100];//到节点1的最短路径值intstate[100]={0};//节点被搜索过状态指示intdata[100][100];//邻接矩阵intpath[100];//从起点到终点的最短路径，0为没在集合，从1开始intindexflag=1;//查找权值最小的节点intfirst=1;//起点intend=7;//终点intfindmin(){intminnode=0,min=MaxNum;for(inti=1;i=n;i++)if((dist[i]min)&&(!state[i]))//state[i]为1时表明该节点入网了{min=dist[i];minnode=i;}returnminnode;}voidmain(){longintdata[n+1][n+1]={{0,0,0,0,0,0,0,},{0,0,400,200,10000,10000,10000},{0,400,0,100,500,10000,1000},{0,200,100,0,800,1000,1000