d算法实现路由最短路径.doc

课程设计说明书 NO.1VC条件下Dijkstra算法求最短路径1课程设计的目的最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。熟悉和掌握Dijkstra算法的应用；学会应用Dijkstra算法解决最短路径问题。2设计方案论证2.1概述Visual C+是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出Visual C+1.0后，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工具。虽然微软公司推出了Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限性，只适用于Windows 2000,Windows XP和Windows NT4.0。所以实际中，更多的是以Visual C+6.0为平台。Visual C+6.0不仅是一个C+编译器，而且是一个基于Windows操作系统的可视化集成开发环境（integrated development environment,IDE）。Visual C+6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。 这些组件通过一个名为Developer Studio的组件集成为和谐的开发环境。算法具体的形式包括：确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题；确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题；确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径等。用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径算法”。 最常用的路径算法有：Floyd-Warshall算法、Dijkstra算法。Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。核心思路通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=a(i,j) nn开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。采用的是松弛技术，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n3)。Dijkstra算法是由荷兰计算机科学家艾兹格迪科斯彻发现的。算法解决的是有向图中最短路径问题。Dijkstra算法是一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。 沈 阳 大 学课程设计说明书 NO.2举例来说，如果顶点表示城市，而边上的权重表示著城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。 Dijkstra 算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个边，都是两个顶点所形成的有序元素对。 (u,v)表示从顶点u到v有路径相连。我们以E所有边的集合，而边的权重则由权重函数w: E 0, 定义。因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径 上所有边的花费值总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。这个算法也可以找到从一个顶点s到任何其他顶点的最短路径。 2.2 Dijkstra算法基本步骤令：并令：(1)对，求。(2)求得，使=令(3)若则已找到到的最短路距离，否则令从中删去转1第一步 先取意即到的距离为0,而是对所赋的初值。第二步 利用已知,根据对进行修正。第三步 对所有修正后的求出其最小者。其对应的点是所能一步到达的点中最近的一个,由于所有。因此任何从其它点中转而到达的通路上的距离都大于直接到的距离,因此就是到的最短距离,所以在算法中令并从s中删去,若k=n则就是到的最短路线, 沈 阳 大 学课程设计说明书 NO.3计算结束。否则令回到第二步,继续运算,直到k=n为止。表1各个顶点的距离：6个顶点10条边起始顶点目的顶点距离AB2AD1AC5DB2DC3DE1BC3EC1EF2CF5其路径图为： 沈 阳 大 学课程设计说明书 NO.4 ADBECF5212331152图1 路径图Dijkstra算法代码为：#include#include#include#include#define MAX_NAME 10#define MAX_VERTEX_NUM 26 typedef char VertexTypeMAX_NAME;typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; /邻接距阵struct MGraph/定义网VertexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; ;int LocateVex(MGraph G,VertexType u)/定位 int i;for(i=0;iG.vexnum;+i)if(strcmp(u,G.vexsi)=0)return i;return -1;void CreateDN(MGraph &G)/建网 沈 阳 大 学课程设计说明书 NO.5int i,j,k,w;VertexType va,vb;printf(请输入有向网G的顶点数和弧数(以空格作为间隔)n);scanf(%d %d,&G.vexnum,&G.arcnum);printf(请输入%d个顶点的值(%d个字符):n,G.vexnum,MAX_NAME);for(i=0;iG.vexnum;+i) scanf(%s,G.vexsi);for(i=0;iG.vexnum;+i) for(j=0;jG.vexnum;+j)G.arcsij=0x7fffffff;printf(请输入%d条弧的弧尾 弧头 权值(以空格作为间隔): n,G.arcnum);for(k=0;kG.arcnum;+k)scanf(%s%s%d%*c,va,vb,&w); i=LocateVex(G,va);j=LocateVex(G,vb);G.arcsij=w; typedef int PathMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef int ShortPathTableMAX_VERTEX_NUM; void ShortestPath_DIJ(MGraph G,int v0,PathMatrix P,ShortPathTable D) int v,w,i,j,min;int finalMAX_VERTEX_NUM; for(v=0;vG.vexnum;+v)finalv=0; Dv=G.arcsv0v; for(w=0;wG.vexnum;+w)Pvw=0; if(Dv0x7fffffff) Pvv0=Pvv=1; Dv0=0; finalv0=1; for(i=1;iG.vexnum;+i) 沈 阳 大 学课程设计说明书 NO.6min=0x7fffffff; for(w=0;wG.vexnum;+w)if(!finalw&Dwmin) v=w;min=Dw;finalv=1; for(w=0;wG.vexnum;+w) if(!finalw&min0x7fffffff&G.arcsvw0x7fffffff&(min+G.arcsvwDw) Dw=min+G.arcsvw; for(j=0;jG.vexnum;+j) Pwj=Pvj;Pww=1;int main()int i,j;MGraph g;PathMatrix p; ShortPathTable d; CreateDN(g); ShortestPath_DIJ(g,0,p,d); /以g中位置为0的顶点为源点，球其到其余各顶点的最短距离。存于d中printf(最短路径数组pij如下:n);for(i=0;ig.vexnum;+i)for(j=0;jg.vexnum;+j)printf(%2d,pij);printf(n);printf(%s到各顶点的最短路径长度为：n,g.vexs0);for(i=0;ig.vexnum;+i)if(i!=0)if(di-0x7fffffff)printf(%s-%s:%dn,g.vexs0,g.vexsi,di);else 沈 阳 大 学课程设计说明书 NO.7printf(%s-%s:无路n,g.vexs0,g.vexsi);system(PAUSE);return 0;3设计结果与分析3.1运行结果图2 输入数据 沈 阳 大 学课程设计说明书 NO.8图3 运行结果3.2结果分析利用Dijkstra算法给出顶点和边的个数，经过程序的计算的出最短路由的矩阵，其计算过程是：表2 算法的计算过程NBCDEFA251A,D242A,D,E2314A,B,D,E3124A,B,C,D,E2124A,B,C,D,E,F2312 沈 阳 大 学课程设计说明书 NO.9得出最短的路径图为：ADBECF21112图4 最短路径图在VC+6.0运行环境中程序以A节点为源节点生成最短路径，它的产生过程是：建立一个以源节点A为根的最短路径树，直到包括最远的节点在内为止。第k步，计算到离源节点最近的k个节点的最短路径。这些路径定义在集N内。本程序将最短路理论应用到实际生活中，尤其是在实际的应用中的应用具有很重要的意义。将实际生活中出现的安全隐患尽量降低，同时也凸显出学习和应用最短路问题原理的重要性。另外，最短路问题在城市道路建设、物资供应站选址等问题上也有很重要的作用。分析和研究最短路问题趋于热门化。4设计体会通过该课程设计，全面系统的理解了编译原理程序构造的一般原理和基本实现方法。把死板的课本知识变得生动有趣，激发了学习的积极性。使我加深了对课堂抽象概念的理解,巩固了课堂上所学的理论知识,并且很好地理解与掌握信号处理中的采样与重构的基本概念、基本原理、基本分析方法，同时培养了我的综合设计能力与实际工作能力，综合素质得到较大提高。这次课程设计的基本目的在于运用学习成果，检验学习成果。课程设计中程序比较复杂，在调试时应该仔细，在程序调试时，注意指针，将不必要的命令去除。在这次课程设计中，我就是按照实验指导的思想来完成。加深了理解文件系统的内部功能及内部实现，培养实践动手能力和程序开发能力的目的。运用学习成果，把课堂上学到的系统化的理论知识，尝试性地应用于实际设计工作，并从理论的高度对设计工作的现代化提出一些有针对性的建议和设想。同时它也检验课堂学习与实际工作到底有多大距离，并通过综合分析，找出学习中存在的不足，以便为完 沈 阳 大 学课程设计说明书 NO.10善学习计划，改变学习内容与方法提供实践依据。对于我们来说，实际能力的培养至关重要，而这种实际能力的培养单靠课堂教学是远远不够的，必须从课堂走向实践。课是通过对软件开发流程的了解，进一步激发了我们对专业知识的兴趣，并能够结合实际程设计达到了专业学习的预期目的。在一个星期的课程设计之后，我们普遍感