文档介绍：课程设计说明书
VC条件下Dijkstra算法求最短路径
最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。
熟悉和掌握Dijkstra算法的应用;学会应用Dijkstra算法解决最短路径问题。
Visual C++是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出Visual C++,随着其新版本的不断问世,Visual C++已成为专业程序员进行软件开发的首选工具。虽然微软公司推出了Visual C++.NET(Visual C++),但它的应用的很大的局限性,只适用于Windows 2000,Windows XP和Windows 。所以实际中,更多的是以Visual C++。
Visual C++++编译器,而且是一个基于Windows操作系统的可视化集成开发环境(integrated development environment,IDE)。Visual C++,包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。这些组件通过一个名为Developer Studio的组件集成为和谐的开发环境。
算法具体的形式包括:确定起点的最短路径问题- 即已知起始结点,求最短路径的问题;确定终点的最短路径问题- 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题;确定起点终点的最短路径问题- 即已知起点和终点,求两结点之间的最短路径等。用于解决最短路径问题的算法被称做“最短路径算法”, 有时被简称作“路径算法”。
最常用的路径算法有:Floyd-Warshall算法、Dijkstra算法。
Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。核心思路通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i,j)] n×n开始,递归地进行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求最短路的图不能有负权边,因为扩展到负权边的时候会产生更短的距离,有可能就破坏了已经更新的点距离不会改变的性质。
沈阳大学
课程设计说明书
举例来说,如果顶点表示城市,而边上的权重表示著城市间开车行经的距离。 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的最低花费路径(. 最短路径)。这个算法也可以找到从一个顶点s到任何其他顶点的最短路径。
Dijkstra算法
基本步骤
令:
并令:
(1)对,求。
(2)求得,使=
令
(3)若则已找到到的最短路距离,否则令从中删去转1
第一步先取意即到的距离为0,而是对所赋的初值。
第二步利用已知,根据对进行修正。
第三步对所有修正后的求出其最小者。其对应的点是所能一步到达的点中最近的一个,由于所有。因此任何从其它点中转而到达的通路上的距离都大于直接到的距离,因此就是到的最短距离,所以在算法中令并从s中删去,若k=n则就是到的最短路线,
沈阳大学
课程设计说明书
计算结束