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