数据结构课程设计报告
题目：北海公园主要游览景点之间最短距离问题
一、课程设计题目：北海公园主要游览景点之间最短距离问题 二、问题定义：（由教师指定）
图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径。并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求
解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。
三、需求分析
1、设计北海公园的平面图。选取若干个有代表性的景点抽象成一个无向带权图，以图
中顶点表示公园内各景点，边上的权值表示两景点之间的距离。 2、输入的形式：整型数字
输入值的范围：0-10
3、输出的形式：由二元组表示以邻接矩阵存储的图
4、程序所能达到的功能；
（1）输出顶点信息：将公园内各景点输出。
（2）输出边的信息：将公园内每两个位置的距离输出。
（3）修改：修改两个位置的距离，并重新输出每两个位置的距离；
（4）求最短路径：输出给定两点之间的最短路径的长度及途经的地点，输出任意
一点与其他各点的最短路径。 （5）删除：删除任意一条边。 （6）插入：插入任意一条边。 5、算法涉及的基本理论分析： 定义邻接矩阵adjmatrix； 自定义顶点结构体VertexType；
定义邻接表中的边结点类型edgenode； switch算法；
狄克斯特拉法（Dijkstra）求任意两结点之间的最短路径； 6、题目研究和实现的价值。
四、算法设计
1、概要设计
（1）存储结构设计
本系统采用图结构类型存储抽象北海公园地图的信息。其中：各景点间的
邻接关系用图的邻接矩阵类型（adjmatrix）存储；景点（顶点）信息用结构数组（VertexType）存储，其中每个数组元素是一个结构变量，包含景点编号、景点名称两个分量；图的顶点个数由分量MaxVertexNum表示，它是整型数据。