基于C# Dijkstra 算法实现的（WinForm）最短路径规划【100012021】

# 基于 Dijkstra 算法的最短路径规划 本小组项目基于 Dijkstra 算法，以武汉大学范围（文理学部，工学部，信息学部）为例，设计两种模式—地名输入模式和自由选点模式，并根据输入地名或选择点位自动规划出起点与终点间的最短路径在地图上予以显示，同时显示路径转点和总距离。数据源来自 OpenStreetMap,经过 Arcmap 处理。 ## 架构设计 本程序为 C#语言编写的窗体应用程序(DijkstraForRoutePlanning.exe)，其中包含了一个类库(Dijkstra.dll),若干控件和相应的文件操作以实现目标功能。 ## 一、流程图  ## 二、Dijkstra.dll 类库中包含了三个类：structure.cs, read.cs 和 compute.cs，分别用于存放各种结构体，读取文件和算法计算。其中， structure.position()用于存放兴趣点，存有地名以及经纬度； structure.road()存放路径信息； structure.node()存放节点信息； read.road()读取路径信息并存储； read.road2node()将路径信息转换为节点信息； read.poi()读取兴趣点信息并存储； compute.shortestPath()用于计算最短路径。 ## 三、Form1.cs[设计] 程序窗体包含了一个 ToolStripMenu,一个 DataGridView,四个 Lable,四个 TextBox,两个 Button 和一个 PictureBox 共 6 类，13 个控件并全部实现了功能。其中， ToolStripMenu 用于导入兴趣点文件，如果没有额外的兴趣点文件，将采用默认的兴趣点文件（包含地名和经纬度的文件）。 DataGridView 显示兴趣点的名称（各种地标名称）， TextBox 分别用于读取或者出发地、目的地和显示路径距离、路径轨迹， PictureBox 用于显示地图和路径， Button 用于选择地名输入模式或自由选点模式。 ## 四、Form1.cs 应用程序的主体。窗体初始化，调用类库中的类设计了若干方法和事件。 事件 Form1_Load_1()：在窗体加载完成时在 DataGridView 中显示兴趣点地名，供用户在地名输入模式下选择出发地和目的地； 方法 InputPoi_ComputeAndDraw()：地名输入模式路径规划的实现方法； 方法 FreeSection_ComputeAndDrawf()：自由选点模式路径规划的实现方法； 事件 button1_Click_1()：执行地名输入模式； 事件 butoon2_Click_2()：执行自由选点； 事件 pictureBox1_MouseClick()：自由选点中标记出发地和目的地； 方法 Near()：寻找兴趣点距离最近的节点； 事件 导入兴趣点文件 ToolStripMenuItem_Click()：导入兴趣点文件。 关键技术 ## 五、Dijkstra 算法 ## 5.1 简介 Dijkstra 算法 1959 年由 E.W.Dijkstra 提出，又称标号法。基本思想：按最短路径长度递增的顺序，逐个产生各最短路径。不仅可以求出起点到终点的最短路径及其长度，而且可以求出起点到其他任何一个顶点的最短路径及其长度 ## 5.2 原理与步骤 用带权的邻接矩阵 Cost 来表示带权的 n 个节点的有向图，Cost[i,j]表示弧 <   的权值，如果从  到  不连通，则 Cost[i,j]=∞。下图表示了一个带权有向图以及其邻接矩阵引进一个辅助向量 Dist，每个分量 Dist[i]表示从起始点到每个终点  的 最短路径长度。假定起始点在有向图中的序号为 i0，并设定该向量的初 始值为： Dist[i]=Cost[  ,i]  ∈V。 令 S 为已经找到的从起点出发的最短路径的终点的集合。 选择  ，使得 Dist[j]=Min{ Dist[i]}  ∈V-S}  ∈V。  就是当前求得的一条从 vi0 出发的最短路径的终点，令 S=S∪{vj} 修改从  出发到集合 V-S 中任意一顶点  的最短路径长度。 如果 Dist[j]+Cost[j,k]<Dist[k] 则修改 Dist[k]为： Dist[k]=Dist[j]+Cost[j,k] 重复第 2、3 步操作共 n-1 次，由此求得从  出发的到图上各 个顶点的最短路径是依路径长度递增的序列。 ## 六、画图 本程序采用 PictureBox 作为画板，根据数据中的路径信息，采用 DrawLine 将地图画出，其中还涉及了经纬度转换到像素坐标系中的过程。 **结论** 各组件能够正常运行并实现全部功能。程序所规划的最短路径与实际符合的较好，与 arcgis 中的路径规划结果一致，用户界面整洁美观，简单易用，符合要求。