d算法实现路由最短路径

《d算法实现路由最短路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程设计说明书NO.1VC条件下Dijkstra算法求最短路径1．课程设计的目的最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。熟悉和掌握Dijkstra算法的应用；学会应用Dijkstra算法解决最短路径问题。2．设计方案论证2.1概述VisualC++是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出VisualC++1.0后，随着其新版本的不断问世，VisualC++已成为专业程序员进行软件开发的首选工具。虽然微软公司推出了VisualC++.NET(VisualC++7.0)，但它的应用的很大的局限性，只适

2、用于Windows2000,WindowsXP和WindowsNT4.0。所以实际中，更多的是以VisualC++6.0为平台。VisualC++6.0不仅是一个C++编译器，而且是一个基于Windows操作系统的可视化集成开发环境（integrateddevelopmentenvironment,IDE）。VisualC++6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导ClassWizard等开发工具。这些组件通过一个名为DeveloperStudio的组件集成为和谐的开发环境。算法具体的形式包括：确定起点的最短路径问题-即已知起始结点，求最短路径的问题；

3、确定终点的最短路径问题-与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题；确定起点终点的最短路径问题-即已知起点和终点，求两结点之间的最短路径等。用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Floyd-Warshall算法、Dijkstra算法。Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。核心思路通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i,j)]n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地

4、公式由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算法是一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于

5、不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。沈阳大学课程设计说明书NO.2举例来说，如果顶点表示城市，而边上的权重表示著城市间开车行经的距离。Dijkstra算法可以用来找到两个城市之间的最短路径。Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。我们以E

6、所有边的集合，而边的权重则由权重函数w:E→[0,∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e.最短路径)。这个算法也可以找到从一个顶点s到任何其他顶点的最短路径。2.2Dijkstra算法基本步骤令：并令：(1)对，求。(2)求得，使=令(3)若则已找到到的最短路距离，否则令从中删去转1第一步先取意即到的距离为0,而是对所赋的初值。第二步利用已知,根据对进行修正。第三步对所有修正后的求出其

7、最小者。其对应的点是所能一步到达的点中最近的一个,由于所有。因此任何从其它点中转而到达的通路上的距离都大于直接到的距离,因此就是到的最短距离,所以在算法中令并从s中删去,若k=n则就是到的最短路线,沈阳大学课程设计说明书NO.3计算结束。否则令回到第二步,继续运算,直到k=n为止。表1各个顶点的距离：6个顶点10条边起始顶点目的顶点距离AB2AD1AC5DB2DC3DE1BC3EC1EF2CF5其路径图为：沈阳大学课程设