下载后可任意编辑一、问题分析和任务定义：[课题 16]选择合适的结构表示图，在此基础上实现求解最短路径的 Floyd 算法。[要求]：对所设计的图结构，提供必要的基本功能。1.1 问题分析：本课题要求用 Floyd 算法解决两个点间的的最短路径问题，首先需要有一个有向图，可以选用邻接矩阵、邻接表和边集数组三种来存储的，考虑到稀疏矩阵的问题，我们可以采纳了领接矩阵来进行存储，存储每对节点的起点，终点和权值。对于两点间的最短路径的算法，应可以求我们输入的任意两点的最短路径，也可以求所有节点的最短路径，最短路径也即是两节点间所有通路中最短的一条，将它输出。可以方便我们让一些具体的事件的最优化。比如说交通图的最短路程问题等，都可以在本算法上进行引升，会非常的方便。1.2 解决思路：提供一个输入接口和标准的输入形式，让用户可以通过输入一组数据建立一个图，在屏幕上以邻接矩阵显示。通过 floyd 算法计算，可得出图中每对顶点的最短路径和路径长度。提供一个查询接口，通过输入起始顶点和终止顶点的代号，输出最短路径和路径长度。也可以查询全部的最短路径，让操作者自行选择。2、任务定义：要注意以下的问题输入输出的问题：2.1 输入数据：顶点 n(范围 0-MVNUM)和边数 e(范围 0 - (n*(n-1))/2)，顶点信息 i,j（字符型）(范围 0 - MVNUM)，边的权值 w ( 整型)2.2 输出数据：建立的邻接矩阵，有向图的邻接矩阵，最短路径和最短路径长度（范围 0–MANUM）2.3 算法所能达到的功能：求得任意两点间最短路径和路径长度输出显示。3、测试数据： 测试的数据组第一组第二组节点数边数3 33 3边的信息1 2 72 3 91 3 21 2 32 3 41 3 11矩阵输出∞ 7 ∞∞ ∞ 9∞ ∞ ∞∞ 3 11∞ ∞ 4∞ ∞ ∞输 出 最 短 路径：① 1->2:路径长度为：7 路径为：1->2② 1->3:路径长度为：2 路径为：1->3③ 2->1:不存在路径④ 2->3:路径长度为 9 路径为：2->3⑤ 3->1:不存在路径⑥ 3->2:不存在路径①1->2:路径长度为： 3 路径为：1->2②1->3:路径长度为： 7 路径为：1->2->3③ 2->1:不存在路径③2->3:路径长度为： 4 路径为：2->3⑤ 3->1:不存在路径⑥ 3->2:不存在路径1下载后可任意编辑 二、概要设计和数据结构的选择： 本次课程设计的数据的相关定义和主要程序段如下： 1、数据类型的定义typedef char VertexTYpe;//定义顶点的值类型typedef int Adjmatrix;//定义顶...
