.NET500 基于GIS的路径寻优算法研究c#

摘  要
单源路径算法问题是计算机科学、运筹学、地理信息系统和交通诱导、导航系统等领域研究的一个热点。传统的单源路径算法主要有Floyd算法和Dijkstra算法。Floyd算法用于计算所有节点之间的单源路径。Dijkstra算法则用于计算一个节点到其他所有节点的单源路径。Dijkstra算法是已经证明的能得出单源路径的最优解，但它的效率是一个很大的问题。对于具有n个节点的一个图，计算一个节点到图中其余节点单源路径的算法时间复杂度为O(n2)。对于一座大中型城市，地理节点数目可能达到几万个到几十万个，计算单源路径的时间开销将是非常巨大的。
本文首先介绍了演示系统在计算机教学的应用，针对大学计算机高级语言授课特点，结合面向对象程序设计语言Visual Studio.net 2005在数据库应用方面的技术特点，来开发计算机高级语言多媒体教学演示系统。文章对系统总体功能和对单源路径（Dijkstra算法）的动态演示等各部分功能的实现、系统的操作方法进行了说明。同时对算法的发展趋势进行了展望。 本文来自think58 [资料来源：http://THINK58.com]

目  录
摘  要 I
ABSTRACT II
目  录 III
第一章  引  言 1
1.1 最短路径问题介绍 1
1.2 演示系统的现状与前景 1
1.3 最短路径算法介绍 2
1.4新算法——层次图模型算法 3
1.5 系统算法——DIJKSTRA 3
第二章 算法探讨 5
2.1 DIJKSTRA与层次图模型 5
2.2 算法思想 8
2.3 算法的效率分析 10
2.4 算法实现 10
第三章  需求分析 11
3.1.  设计的总目标 11
3.1.1.目标概况 11
3.1.2. 功能划分和描述 11
3.2. 可行性研究 14
3.3 系统环境配置 15
3.3.1. 硬件环境方面的要求 15
3.3.2. 软件环境方面的要求 15
3.3.3. 开发工具简介 15
第四章  系统的模块划分 18
4.1. 系统工作流程 18
4.1.1 算法初始化流程 18
4.1.2 用户控制流程 18
4.1.2 计算路径流程 19
4.2. 系统整体结构与模块划分 20
第五章  系统的功能设计 21
5.1 DIJKSTRA算法分析 21
5.2 各模块的详细设计 23
5.2.1初始化详细设计 23 内容来自think58 [版权所有：http://think58.com]
5.2.2 算法分析 24
5.2.3 执行算法 24
5.2.4 算法演示 27
5.2.5 Flash演示 28
第六章 系统测试与维护 30
6.1 系统测试 30
6.1.1 软件测试 30
6.1.2测试步骤 30
6.2 系统维护 32
第七章 小结 33
7.1 系统优点 33
7.2 系统缺点 33
7.3 设计展望 33
谢辞 34
参考文献 35 think58.com

[资料来源：http://THINK58.com]

基于最短路径算法的复杂性，国内外许多学者对此进行了大量的研究。传统经典的算法有单源节点的Dijkstra算法，所有顶点之间最短路径的Floyd算法。
Dijkstra算法按路径长度递增次序产生最短路径。用V表示图中的点集合，S表示已经加入最短路径中的点集合，引入辅助向量D，每个分量D[i]表示当前所找到的从起始点v到每个终点vi 的最短路径长度。它的初态为：若从v 到vi 有弧，则D[i]为弧上的权值；否则置D[i]为无穷大（实际编程中用机器所能表示的最大数表示）。长度为
D[j]=Min{D[i], vi∈V}
的路径就是从v出发的长度最短的一条路径。此路径为(v, vj)。
假设下一条长度次短的最短路径的终点是vk，则这条路径或者是(v, vj)，或者是(v, vi, vj)。对应长度或者是从v到vk的权值，或者是D[j]和从vj到vk 的弧上的权值之和。
算法描述如下：
1. 假设用带权的邻接矩阵arcs来表示带权有向图，arcs[i][j]表示弧< vi, vj >上的权值。若< vi, vj >不存在，则arcs[i][j]为无穷大。S为已找到的从v出发的最短路径的终点集合，它的初始状态为空集。
2. 选择vj ，使得D[j]=Min{D[i] | vi ∈V-S}, vj 就是当前求得的一条从v出发的最短路径长度的终点。把vj 加入集合S。
3. 修改从v出发到集合V-S上任一顶点vk 可达的最短路径长度。如果D[j]+arcs[j][k]<D[k]则修改D[k]为D[k]=D[j]+arcs[j][k] [资料来源：http://www.THINK58.com]
4. 重复操作(2) (3)n-1。由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。
查找下一条长度次短的最短路径的终点，时间复杂度为O(n)，需要查找n-1次，所以总算法的时间复杂度为O(n2)。由此看来，Dijkstra算法的效率是一个很大的问题。计算一个节点到图中某一特定节点的最短路径与计算一个节点到图中其余节点一样复杂。这样对于一座大中型城市，地理节点数目可能达到几万个到几十万个，计算最短路径的时间开销将是非常巨大的。
Floyd算法用来求每对顶点之间的最短路径。算法时间复杂度达到了O(n3)。
以上是基本的算法。下面算法基本上是以Dijkstra算法为基础，但在不同条件下根据应用需要对Dijkstra算法做了部分修改。以要计算的最短路径的起始点和终止点为焦点，画出一个椭圆，最短路径的计算限制在这个椭圆中。真正最短路径上的点不一定就在这个椭圆内，况且算法的时间复杂度，精确度都跟椭圆范围关系很大，一般认为得到的只是近似解，这是一种有损算法。根据起始点和终止点的方向，在最短路径计算中限制了一定的方向，减少了计算时间。这同样也是一种有损算法。对图进行的层次化的描述，将大平面图分解成较小的子图，预先计算了部分最短路径并进行编码存储，其最佳路径的查询只需查询本地最短路径和计算层间各边界节点连接的最短路径，提高了最短路径的计算效率。但这个算法局限是不能根据路径变化动态改变，如果路径有变，则必须重新计算子图最短路径并编码存储，所以并不能适合交通信息瞬间变化的实际情况。 本文来自think58