一、课程设计题目：校园最短路径问题
二、课程设计目的：
1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；
2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所具备的科学工作方法和作风。
三、课程设计要求：
1.设计的题目要求达到一定的工作量（300行以上代码），并具有一定的深度和难度。
2.编写出课程设计报告书，内容不少于10页（代码不算）。
四、需求分析：
1、问题描述
图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径，并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。
校园最短路径问题中的数据元素有：
a) 顶点数
b) 边数
c) 边的长度
2、功能需求
要求完成以下功能：
a)输出顶点信息：将校园内各位置输出。
b)输出边的信息：将校园内每两个位置（若两个位置之间有直接路径）的
距离输出。
c)修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输
出每两个位置（若两个位置之间有直接路径）的距离。
d)求最短路径：输出给定两点之间的最短路径的长度及途径的地点或输出
任意一点与其它各点的最短路径。
e)删除：删除任意一条边。
f)插入：插入任意一条边。
3、实现要点
a) 对图的创建采用邻接矩阵的存储结构，而且对图的操作设计成了模板类。
为了便于处理，对于图中的每一个顶点和每一条边都设置了初值。
b) 为了便于访问，用户可以先输出所有的地点和距离。
c) 用户可以随意修改两点之间好的距离。
d) 用户可以增加及删除边。
e) 当用户操作错误时，系统会出现出错提示。
五、概要设计:
1.抽象数据类型图的定义如下：
ADT Graph{
数据对象V：V是具有相同特性数据元素的集合，称为顶点集。
数据关系R：
R={VR}
VR={（v，w）| v , w∈V, (v , w)表示v和w之间存在路径}
基本操作P：
CreatGraph(&G, V, VR)
初始条件： V是图的顶点集，VR是图中边的集合。
操作结果：按定义(V, VR) 构造图G。
DestroyGraph(&G)
初始条件：图G已存在。
操作结果：销毁图。
LocateVex(G, u)
初始条件：图G存在，u和G中顶点具有相同特征。
操作结果：若G中存在顶点u，则返回该顶点在图中“位置”；否则返回其它信息。
GetVex(G, v)
初始条件：图G存在，v是G中某个顶点。
操作结果：返回v的信息。
InsertVex(&G, v)
初始条件：图G存在，v和G中顶点具有相同特征。
操作结果：在图G中增添新顶点v。
DeleteVex(&G, v)
初始条件：图G存在，v和G中顶点具有相同特征。
操作结果：删除G中顶点v及其相关的边。
InsertArc(&G, v, w)
初始条件：图G存在，v和w是G中两个顶点。
操作结果：在G中增添弧，若G是无向的，则还增添对称弧。DeleteArc(&G, v, w)
初始条件：图G存在，v和w是G中两个顶点。
操作结果：在G中删除弧，若G是无向的，则还删除对称弧。} ADT Graph
2.主程序
void main()
{
初始化；
while(“命令”!=“退出”)
{
Switch语句
接受命令（输入选择项序号）；
处理命令；
}
}
3.本程序运用函数的调用，只有两个模块，它们的调用关系为：
六、详细设计
（详细见下面的源代码）
typedef struct //图中顶点表示点，存放点名称void Menu() //输出菜单
void PutOutVex(MGraph *G) //输出每个顶点的信息
void PutOutArc(MGraph *G) //输出每条边的信息
void Dijkstra(MGraph * G) //迪杰斯特拉算法求最短路径void DeleteVex(MGraph *G) //删除某个顶点
void DeleteArc(MGraph *G) //删除某条边
void InsertArc(MGraph *G) //插入某条边
void main() //主函数
七、源程序代码
#include
#include
#include
#include
#include
#include
#define MAX 10000
#define MAXLEN 8
#define ADJTYPE int
typedef struct //图中顶点表示点，存放点名称{
char name[30];
int num;
}VEXTYPE;
typedef struct
{
VEXTYPE vexs[MAXLEN]; //顶点的信息
ADJTYPE arcs[MAXLEN][MAXLEN]; //邻接矩阵
int vexnum,arcnum ; //顶点数和边数
}MGraph;
MGraph b;
MGraph InitGraph()
{ /*建立无向网的邻接矩阵结构*/ int i, j;
MGraph G;
G.vexnum =8; //存放顶点数
G.arcnum =13; //存放边点数
for(i=0;i
