d算法实现路由最短路径
课程设计说明书 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(n^3)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 存于d中printf("最短路径数组p[i][j]如下:\n");for(i=0;i 第k步，计算到离源节点最近的k个节点的最短路径这些路径定义在集N内本程序将最短路理论应用到实际生活中，尤其是在实际的应用中的应用具有很重要的意义将实际生活中出现的安全隐患尽量降低，同时也凸显出学习和应用最短路问题原理的重要性另外，最短路问题在城市道路建设、物资供应站选址等问题上也有很重要的作用分析和研究最短路问题趋于热门化4．设计体会通过该课程设计，全面系统的理解了编译原理程序构造的一般原理和基本实现方法把死板的课本知识变得生动有趣，激发了学习的积极性使我加深了对课堂抽象概念的理解,巩固了课堂上所学的理论知识,并且很好地理解与掌握信号处理中的采样与重构的基本概念、基本原理、基本分析方法，同时培养了我的综合设计能力与实际工作能力，综合素质得到较大提高这次课程设计的基本目的在于运用学习成果，检验学习成果课程设计中程序比较复杂，在调试时应该仔细，在程序调试时，注意指针，将不必要的命令去除在这次课程设计中，我就是按照实验指导的思想来完成加深了理解文件系统的内部功能及内部实现，培养实践动手能力和程序开发能力的目的运用学习成果，把课堂上学到的系统化的理论知识，尝试性地应用于实际设计工作，并从理论的高度对设计工作的现代化提出一些有针对性的建议和设想。 同时它也检验课堂学习与实际工作到底有多大距离，并通过综合分析，找出学习中存在的不足，以便为完 沈 阳 大 学课程设计说明书 NO.10善学习计划，改变学习内容与方法提供实践依据对于我们来说，实际能力的培养至关重要，而这种实际能力的培养单靠课堂教学是远远不够的，必须从课堂走向实践课是通过对软件开发流程的了解，进一步激发了我们对专业知识的兴趣，并能够结合实际程设计达到了专业学习的预期目的在一个星期的课程设计之后，我们普遍感到不仅实际动手能力有所提高，更重要的存在的问题在专业领域内进行更深入的学习5．参考文献[1]鲜继清．现代通信系统.西安：西安电子科技大学出版社,2003.2：342-356[2]唐宝民．通信网基础[M].北京：机械工业出版社,2004：300-303[3]郑阿奇．Visual C++实用教程.北京：电子工业出版社,2007：140-164[4]唐宝明，张颖. 通信网基础[M].北京：机械工业出版社2007-12：300-301[5]魏亮，李春葆. Visual C++程序设计例学与实践[M].北京：清华大学出版社2006-6：45-98 沈 阳 大 学。
