基于Dijkstra算法的路由选择

1、基于Dijkstra算法的路由选择姓名：班级：学号：摘要：本文阐述了最短路径问题及其算法，采用迪克斯屈拉算法解决最短路由问题。最短路由的问题利用了图的描述，并把算法用C+胡言来实现，这就很好地将所学知识和现实生活结合起来。关键词：最短路径Dijkstra算法C+随着现代通信技术的不断发展，通信网的范围也逐渐扩大，通信网已成为人们生活中不可或缺的一部分了。而随着人们之间通信次数的增加，使的通信网的通信量也随之大量增加。这给通信网带了沉重的负担。如何在现有通信网的基础上提高通信效率，网络利用率和网络可靠性，以满足人们日益增长的对网络通信能力的需求已成为对通信网研究的主要内容。迪克斯屈拉算法是最适合

2、解决网络拓扑中两节点间的最短通信距离的问题的方法之一。本文就如何利用迪克斯屈拉算法解决网络中点到点通信的最短距离问题做了说明，以此提高通信网的通信效率。一、迪克斯屈拉算法1、算法介绍迪克斯屈拉算法是由荷兰计算机科学家迪克斯屈拉(Dijkstra)于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负

3、权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。Dijkstra(迪克斯屈拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，该算法要求图中不存在负权边。ProcedureDijkstra(G:所有权都为正数的加权连通简单图)G带有定点a=V0,v1,Vn=z和权w(Vi,vj),若vi,vj不是G中的边，则w(vi,vj)=0°Fori:=1tonL(vi):=00L(a):=0S:=小初始化标记，a的标记为0

4、,其余结点标记为0°,S是空集Whilez错误！未找到引用源。Sbegin5=不属于S的L(u)最小的一个顶点S:=S错误！未找到引用源。ufor所有不属于S的顶点vifL(u)+w(u,v)<L(v)thenL(v):=L(u)+w(u,v)这样就给S中添加带最小标记的顶点并且更新不在S中的顶点标记endL(z)=从a到z的最短路的长度2、根据Dijkstra算法给出的定理定理1迪克斯屈拉算法求出连通简单无向加权图中的两个顶点之间最短路的长度。迪克斯屈拉算法通过一步一步的迭代求出最短路径，假设在第k次迭代中。在s中的顶点v的标记L(v)是从a到这个顶点v的最短路的长度。不在s

5、中的顶点的标记是(除了这个顶点自身之外)只经过s中顶点的从a到这个顶点的最短路的长度。设u是第k次迭代结束时带最小标记的不在s中的顶点(若该顶点不唯一，可采用带最小标记的任意顶点)。在第k+1次迭代中，u是添加到s中的顶点，则在第k+1次迭代中，u的标记必须是a到u的最短路的长度。否则，k次迭代后，从结点a到某个结点l的路，其路得长度小于Lk(v)0定理2迪克斯屈拉算法使用O(n2)次运算(加法和比较)来求出n阶连通简单无向加权图中两个顶点之间最短路的长度，求加权无向图中最短路的Dijkstra算法可以推广到求加权有向图中最短有向路。定理3设有向图G中不含长度非正的有向圈，并且从点1到其余各点

6、都有有限长的有向路，那么G中结点1到其余各点j的最短有向路长度S有唯一有限解Sj。定理4设Sj是加权有向图G中自结点1到结点j的最短有向路的长度，并且对所有的j=1,2,3,，n,S为有限值。若图G中除结点1外的其余各点能重新编写成如下的序号2,3,，n使得对所有i<j,成立S&G错误！未找到引用源。且w<j,i>>0或者S>S且w<j,i>=错误！未找到引用源。，即<j,i>错误！未找到引用源。E(G),则错误！未找到引用源。定理5设G=<V,E纪一个边权为正值的有向图，其中V=1,2,3，n。则在G中，任意一条最短有向路得

7、长都大于它的真子有向路的长。Dijkstra算法求出了图中一个特定顶点到其他各定点的最短路，可以利用Dijkstra算法解决实际生活中的一些问题。二、Dijkstra算法的实际应用1、问题的提出在现实生活中，我们常常会遇到很多问题，都是要找到一个地方到另一个地方的最短路径，当然还要满足各方面的要求，包括可实现性、预算、带来的利益等各方面条件。比如Dijkstra算法在计算机网络路由问题中的应用。通常我们解决的办法就是找到一条距离最短，又在现实可接受范围内的路径。2、运用Dijkstra算法解决实际问题在通信网中，如何利用现有的通信网络，通过最短的通信路径完成信息的传递，在通信网研究中具有重要意

8、义。为了降低研究复杂性，我们假设每条通信线路的通信系能和状况都一样且恒定不变。建立如下网络模型：点用来表示路由节点（用a到e及z表示），边用来表示两节点间的通信线路，边上的权重表示两节点间的距离，节点本身到他自己的距离记为0,如果两节点没有边直接相连用8表示。图1无向图G利用Dijkstra算法实现求解最短路径问题要有边权。本文最佳路径是基于两个路由节点间的距离。因此找路由节点间的最短距离就转化成了找图G=（V,E）中指定两点间的最小距离了。首先我们利用上图可以知道节点之间的邻接关系，为此我们可以先画出节点间的邻接矩阵，方便我们对节点的关系进行了解。如下表（单位：项：abcdeza040020

9、0oooooob4000100500oooocr200100080011000:oodoo5008000200600eoooo100020001300zoooooo6003000下面对最优路径进行分析，我们a为路径的起点，z为终点。初始化：L(a)=0L(b)=L(c)=00,L(d)=00,L(e)=00,L(z)=00,S=，一次迭代：U=aS=aL(a)+W(a,b)=0+400=400<L(b)L(a)+W(a,c)=0+200=200<L(c)L(a)+W(a,d)=0+00=00L(a)+W(a,e)=0+00=00L(a)+W(a,z)=0+00=00L(b)=400

10、,L(c)=200,L(d尸L(e)=L(z)=00二次迭代：U=gS=a,cL(c)+W(c,b)=200+100=300<L(b)L(c)+W(c,d)=200+800=1000VL(d)L(c)+W(c,e)=200+1000=1200VL(e)L(c)+W(c,z)=200+00=00L(b)=300,L(d)=1000,L(e)=1200,L(z)=00三次迭代：U=hS=a,c,bL(b)+W(b,d)=300+500=800<L(d)L(b)+W(b,e)=300+oo=oo>00L(b)+W(b,z)=300+00=00L(d)=800,L(e)=1200,L

11、(z)=00四次迭代：U=dS=a,c,b,dL(d)+W(d,e)=800+200=1000VL(e)L(d)+W(d,z)=800+600=1400VL(z)L(e)=1000,L(z)=1400五次迭代：U=0S=a,c,b,d,eL(e)+W(e,z)=1000+300=1300VL(z)L(z)=1300结束：U=z,S=a,c,b,d,e,z由于终点z已经进入S集合中所以迭代结束。这样就找到了从起点a到终点z的最短路径以及到中间各点的最短路径。本文的算法是在VC+勺环境下实现的，程序的基本思想是基于Dijkstra算法的。这个程序中是以节点1代表a,且以节点1作为初始节点，节点6最

12、为终止节点，在程序中所求的最短路径问题则为从节点1到节点6以及其他中间节点的最短路径。具体的程序代码见附录。为为为为为为度度葭度度度长长长长长长上行雪后廿rtlhe音曲也住住的的的的的的点点点点点点123456点点点点点点ttC七t3嚼sss:srrrrrr-1iirlrlHfFffff020080016601300队fit*“点到©nd点的最为路径为：->3->2->4->5->6Pressanykeytocontinue图2运行结果三、结论通过本学期对计算机算法设计与分析的学习，使我深刻体会到了算法在实际生活中的广泛应用，也使从以前的定向思维上升了一

13、个台阶，学会把抽象的变为具体，能用点、线、图来描述抽象的事物，把很多抽象的知识具体化，使得抽象的知识更容易理解、记忆。计算机算法设计与分析中有很多简便的算法，可以实现很多功能。Dijkstra算法是计算机众多算法中的一种，能够方便的找到两点之间的最短路径，通过上面Dijkstra算法的应用例子可以清楚的看到通过Dijkstra算法可以在很复杂的图中很容易的找到点到点的最短路径，也可以对实际生活中的一些问题给予很大的帮助。参考文献：1王晓东.计算机算法设计与分析第四版.2乐阳，龚健雅.Dijkstra最短路径算法的一种高效率实现.3凡金伟，吕康.基于Dijkstra算法在物流配送中的应用.4徐凤

14、生，李天志.所有最短路径的求解算法J.微计算机应用.附录：#include<iostream.h>#include<stdio.h>#defineMaxNum10000/节点间不是邻居节点#definen6节点数目intdist100;/到节点1的最短路径值intstate100=0;/节点被搜索过状态指示intdata100100;/邻接矩阵intpath100;/从起点到终点的最短路径，0为没在集合，从1开始intindexflag=1;/查找权值最小的节点intfirst=1;/起点intend=7;/终点intfindmin()intminnode=0,min=

15、MaxNum;for(inti=1;i<=n;i+)if(disti<min)&&(!statei)/statei为1时表明该节点入网了min=disti;minnode=i;returnminnode;voidmain()longintdatan+1n+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,10000,0,10000,500,800,0,200,600,0,10000,10000,1000,200,0,300,0,1

16、0000,10000,10000,600,300,0;/*初始化*/for(inti=1;i<=n;i+)disti=data1i;pathi=0;statefirst=1;intdone=1;while(done<n)intnode=findmin();if(node!=0)done+;/找到一个点就加1statenode=1;/标记已经找到了从节点1到节点node的最短路径pathindexflag=node;indexflag+;for(inti=1;i<=n;i+)/更新还没有找到的点的路径值if(disti>distnode+datanodei)&&(!statei)disti=distnode+datanodei;if(node=end)break;elsebreak;for(intp=1;p<=n;p+)/输出最短路径if(distp=MaxNum)cout<<"从first点没有到"<<p<<”点的最短路径为"<<