《数据结构课程设计--用C#语言解决最短路径的问题.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计--用C#语言解决最短路径的问题.doc（14页珍藏版）》请在三一文库上搜索。
1、 数据结构单元设计报告单元设计任务书软件学院 软件开发与项目管理专业 课程名称数据结构单元设计时间2011学年第下学期13周学生姓名指导老师XXX题 目用C#语言解决最短路径问题主要内容：最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。要求：（1）通过实际项目的分析、设计、编码、测试等工作，掌握用C#语言来开发和维护软件。（2）按要求编写课程设计报告书，能正确编写分析、设计、编码、测试等技术文档和用户使用手册。应当提交的文件：（1）单元设计文档。（2）单元设计附件（主要是源程序）。用C#语言解决最短路径的问题 学生姓名： 指导老师：XXXX
2、 摘 要 本单元设计主要解决设计一个程序，用户输入起始位置，就能得到该点到其他点的最短路线，及最短距离。 程序运行平台为Windows 98/2000/XP/7，.net 2.0框架。在程序设计中，采用了C#面向对象编程语言，将功能实现封装在业务类中，对问题中的要求做出了准确的实现。程序通过调试运行，实现了设计目标。 关键词 C#；业务类、业务方法、控制台界面 迪杰斯特拉（Dijkstra）、弗洛伊德（Floyd） 用C#语言解决最短路径问题 1 引 言本单元设计主要解决设计一个程序，用户输入起始位置，就能得到该点到其他点的最短路线，及最短距离。（各点之间的距离要求事先录入）1.1 单元设计目
3、的通过这次单元设计进一步了解了最短路径的算法。1.2 单元设计内容本次单元设计内容主要是利用迪杰斯特拉求解最短路径。最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 算法具体的形式包括： 确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。 确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。 确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。 全局最短路径问题 - 求图中所有的最短路径。2 需求分析 功能名称产生最短路线及最短距离功能描述输入起始位置v0，得到该点到所
4、有点的最短路线，及距离输入数据数字v0 v0v0vn事件流1.运行程序，提示输入一个数字n；2.提交数字后，按输出数据的要求显示输出结果。输出数据1.以多行形式输出路线及距离。思路提示求解最短路径的算法很多，这里采用迪杰斯特拉：按路径长度递增次序产生最短路径算法： 把V分成两组： （1）S：已求出最短路径的顶点的集合 （2）V-S=T：尚未确定最短路径的顶点集合 将T中顶点按最短路径递增的次序加入到S中， 保证：（1）从源点V0到S中各顶点的最短路径长度都不大于 从V0到T中任何顶点的最短路径长度 （2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的
5、只包括S中顶点作中间 顶点的最短路径长度 依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的 直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和3 概要设计3.1 数据结构与数据存储表示这方面使用二维数组nMAXMAX来静态存储不超过MAX行MAX列的距离方阵。3.2 程序结构 主要使用与实现如下类： (1)界面类MagicSquareCon，用于调用业务类，实现最短路线，及距离的输出。(2业务类Dijkstra，用于实现需求分析的功能，主要包括以下方法或属性：int PathArc: 路径下标的数组int ShortPathTable 存储到各点最短路径的权值和ShortP
6、ath(int init) 计算init 点到各顶点的最最短路径3.3 函数逻辑功能调用图MagicSquareConDijkstraPathArcShortPathTableShortPath(int vo)图3.1 逻辑功能调用图4 详细设计（1） int PathArc路径下标的数组 比如PathArc为P:0,0,1,4,2,4,3,6,7，P8=7,它的意思是v0到v8的最短路径，顶点v8的前驱顶点是v7, 再用P7=6 表示v7的前驱是v6,P6=3,表示v6的前驱是v3,这样就得到v0至V8的最短路径为v8-v7-v6-v3-v4-v2-v1-v0,即v0-v1-v2-v4-v3
7、-v6-v7-v8。 （2）int ShortPathTable 存储到各点最短路径的权值和。比如数组为0,1,4,7,5,8 表示v0到v1的距离是1，v0到v4的距离是5。（3）ShortPath(int init) 计算init 点到各顶点最短路径的方法，构造函数调用。3.4 程序执行流程图开始输入nDijkstraShortPath(int vo)PathArc ShortPathTable属性输出最短路线及最短距离结束5 运行环境与结果5.1程序运行环境:VS2008 VS2005开发平台。5.2 程序运行结果 （1）运行程序，根据提示输入指令,当v0=0时，程序运行结果如图4.2.
8、1所示 5 结束语本次单元设计我选择了一个最短路径的算法实现。通过不懈的努力终于掌握这两个经典的算法 迪杰斯特拉（Dijkstra）、弗洛伊德（Floyd）在编程实现的过程中，我进一步掌握和熟悉了而为数组的应用，并熟悉了将问题分解在组装的解决方法和函数的调用。通过这次课程设计，使我们学到了一些以前没有学过的知识，使我们对程序设计有了更深层次的认识和理解，懂得了灵活运用。最后，由衷的向我的指导老师表示衷心的感谢，是她的指导和要求，才使我的课程设计有了较为完善的一面，才有了我能力的提高，并使我得到了充分的锻炼，同时也感谢我的同学，是他们帮助我解决了一些问题。 参考文献1黎明志. 数据结构用C语言描
9、述. 北京：中国水利水电出版社，2006，1附录 源程序代码/ 程序名称：SortPath/ 程序功能：最短路线/ 程序作者：HYH/ 最后修改日期：2011-12-2二维数组构造图：using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace SortPath public class MGraph public int Vexs private set; get; public int, Arc private set; get; public int NumEdges
10、 private set; get; /图的顶点数 public int Width private set; get; / / 图构造器 / / 顶点数 / 二维数组 / 一维数组 public MGraph(int width, int, array,int arrayName) Vexs = arrayName; Arc = array; Width = width; NumEdges = width; 关键算法：using System;using System.Collections.Generic;using System.Linq;using System.Text;namesp
11、ace SortPath public class Dijkstra public int PathArc private set; get; /储存路径下标的数组 public int ShortPathTable private set; get; /存储到各点最短路径的权值和 MGraph mGraph; int numVertexes; public Dijkstra(int vo,MGraph mgraph) mGraph = mgraph; PathArc = new intmgraph.Width; / 路径数组 ShortPathTable = new intmgraph.Wi
12、dth; /路径权值数组 numVertexes = mgraph.Width; ShortPath(vo); private void ShortPath(int init) int v, w, k=0, min; bool final = new boolmGraph.Width; /finalw=true 表示求得顶点v0 至vw的最短路径 for (v = 0; v numVertexes; v+) ShortPathTablev = mGraph.Arcinit, v;/与v0有连线的顶点赋权值 ShortPathTable0 = 0; /v0 至v0 的路径为0 final0 =
13、true; /v0至v0 不需要求路径 for (v = 1; v numVertexes; v+) min = int.MaxValue; for (w = 0; w numVertexes; w+) if(!finalw&ShortPathTablewmin) k=w; min=ShortPathTablew; finalk = true; /讲找到的最近顶点置为true for (w = 0; w numVertexes; w+) if (!finalw & (Convert.ToInt64(mGraph.Arck, w)+min ShortPathTablew) ShortPathTa
14、blew = mGraph.Arck, w + min ; PathArcw = k; 界面层：using System;using System.Collections.Generic;using System.Linq;using System.Text;using SortPath;namespace PathTest class Program static int vwrtexes = 9; /顶点 int Varray = new intvwrtexes; int, edgesArray = new intvwrtexes, vwrtexes; static MGraph Mg;
15、static void Main(string args) int init = 0; /出发启始位置 Program p = new Program(); p.Init(); Mg= new MGraph(vwrtexes, p.edgesArray, p.Varray); Dijkstra di = new Dijkstra(init, Mg); int Path = di.ShortPathTable; int Arc = di.PathArc; Console.WriteLine(输入起始位置：); init = Convert.ToInt32(Console.ReadLine();
16、p.Show(Arc, Path, init); 将各点之间的距离 初始化到二维数组中 private void Init() for (int i = 0; i vwrtexes; i+) Varrayi = i; for (int j = 0; j vwrtexes; j+) edgesArrayi, j = int.MaxValue; if (i = j) edgesArrayi, j = 0; edgesArray0, 1 = 1; edgesArray0, 2 = 5; edgesArray1, 2 = 3; edgesArray1, 3 = 7; edgesArray1, 4 =
17、5; edgesArray2, 4 = 1; edgesArray2, 5 = 7; edgesArray3, 4 = 2; edgesArray3, 6 = 3; edgesArray4, 5 = 3; edgesArray4, 6 = 6; edgesArray4, 7 = 9; edgesArray5, 7 = 5; edgesArray6, 7 = 2; edgesArray6, 8 = 7; edgesArray7, 8 = 4; for (int i = 0; i vwrtexes; i+) for (int j = i; j vwrtexes; j+) edgesArrayj,
18、i = edgesArrayi, j; 显示最短路线信息 及最短距离 private void Show(int arc,int path,int v) Console.WriteLine(最短路径倒序如下：); for (int i = 1; i vwrtexes; i+) Console.Write(v0-v1, v, i); int j = i; while (arcj != 0) Console.Write( + arcj); j = arcj; Console.WriteLine(); Console.WriteLine(nn源点到各顶点的距离:); for (int i = 1; i vwrtexes; i+) Console.WriteLine(v0-v1:2,v,Mg.Vexsi,pathi);