数据结构课程设计--用C#语言解决最短路径的问题.doc

《数据结构》单元设计报告 单元设计任务书 软件学院 软件开发与项目管理专业 课程名称 数据结构单元设计 时间 2011学年第下学期13周 学生姓名 指导老师 XXX 题 目 用C#语言解决最短路径问题 主要内容： 　最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 要求： （1）通过实际项目的分析、设计、编码、测试等工作，掌握用C#语言来开发和维护软件。 （2）按要求编写课程设计报告书，能正确编写分析、设计、编码、测试等技术文档和用户使用手册。 应当提交的文件： （1）单元设计文档。 （2）单元设计附件（主要是源程序）。 用C#语言解决最短路径的问题 学生姓名： 指导老师：XXXX 摘 要 本单元设计主要解决设计一个程序，用户输入起始位置，就能得到该点到其他点的最短路线，及最短距离。 程序运行平台为Windows 98/2000/XP/7，.net 2.0框架。在程序设计中，采用了C#面向对象编程语言，将功能实现封装在业务类中，对问题中的要求做出了准确的实现。程序通过调试运行，实现了设计目标。 关键词 C#；业务类、业务方法、控制台界面 迪杰斯特拉（Dijkstra）、弗洛伊德（Floyd） 1 引 言 本单元设计主要解决设计一个程序，用户输入起始位置，就能得到该点到其他点的最短路线，及最短距离。（各点之间的距离要求事先录入） 1.1 单元设计目的 通过这次单元设计进一步了解了最短路径的算法。 1.2 单元设计内容 本次单元设计内容主要是利用迪杰斯特拉求解最短路径。 最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 算法具体的形式包括： 　　 确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。 　　 确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。 　 　确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。 全局最短路径问题 - 求图中所有的最短路径。 2 需求分析 功能名称 产生最短路线及最短距离 功能描述 输入起始位置v0，得到该点到所有点的最短路线，及距离 输入数据 数字v0 v0{v0`vn} 事件流 1.运行程序，提示输入一个数字n； 2.提交数字后，按输出数据的要求显示输出结果。 输出数据 1.以多行形式输出路线及距离。  思路提示 求解最短路径的算法很多，这里采用迪杰斯特拉： 按路径长度递增次序产生最短路径算法： 　　把V分成两组： 　　（1）S：已求出最短路径的顶点的集合 　　（2）V-S=T：尚未确定最短路径的顶点集合 　　将T中顶点按最短路径递增的次序加入到S中， 　　保证：（1）从源点V0到S中各顶点的最短路径长度都不大于 　　从V0到T中任何顶点的最短路径长度 　　（2）每个顶点对应一个距离值 　　S中顶点：从V0到此顶点的最短路径长度 　　T中顶点：从V0到此顶点的只包括S中顶点作中间 　　顶点的最短路径长度 　　依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的 　　直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和 3 概要设计 3.1 数据结构与数据存储表示 这方面使用二维数组n[MAX][MAX]来静态存储不超过MAX行MAX列的距离方阵。 3.2 程序结构 主要使用与实现如下类： (1)界面类MagicSquareCon，用于调用业务类，实现最短路线，及距离的输出。 (2业务类Dijkstra，用于实现需求分析的功能，主要包括以下方法或属性： int[] PathArc: 路径下标的数组 int[] ShortPathTable 存储到各点最短路径的权值和 ShortPath(int init) 计算init 点到各顶点的最最短路径 3.3 函数逻辑功能调用图 图3.1 逻辑功能调用图 4 详细设计 int[] PathArc路径下标的数组 比如PathArc为P:{0,0,1,4,2,4,3,6,7}，P[8]=7,它的意思是v0到v8的最短路径，顶点v8的前驱顶点是v7, 再用 P[7]=6 表示v7的前驱是v6,P[6]=3,表示v6的前驱是v3,这