数据结构
设计说明书
单源点最短路径算法的实现
学生姓名王文刚
学号1418064056
班级网络1402
成绩
指导教师
数学与计算机科学学院
年月日
课程设计任务书
20 —20 学年第学期
课程设计名称：数据结构课程设计
课程设计题目：单源点最短路径算法的实现
完成期限：自年月日至年月日共 2 周设计内容：
1.任务说明
2.要求
3.参考资料
指导教师：教研室负责人：
课程设计评阅
摘要
设计了一求解最短路径的方法，该方法具有在输入的途中查找两个顶点之间的最短路径的功能。本方法采用VC++作为软件开发环境，采用Dijkstar函数来求取顶点之间的最短路径。，用户可以自己输入各个地点及其之间的距离，便于用户在不同情况下均可使用。
关键词：最短路径；Dijkstar；无向图;
目录
目录
1课题描述 (2)
2 需求分析 (3)
3概要设计 (4)
3.1 存储结构 (4)
3.2 算法描述 (5)
4详细设计 (6)
4.1 功能模块图 (6)
4.2 主函数 (6)
4.3 pd函数 (7)
4.4 CreateMGraph函数 (8)
4.5Dijkstar函数 (9)
5程序编码 (11)
6程序的调试与测试 (15)
8总结 (16)
参考文献 (17)
1.目录中可以只有一级标题
2.页码右侧对齐页边距
3.本页不需要页码
4.以上内容仅作参考，具体章节由课程设计类型确定
1课题描述
随着交通的发展，人民生活水平的提高。出门旅行变的越来越频繁，而且供暖也成为冬天不可或缺的内容。为了节约时间和金钱，所以人们都希望找到旅行目的地的最短路径和架设暖气的最短路径。那么如何找到最短路径呢？由于路径较多，手工计算比较麻烦，而且容易出错，因此人们用计算机语言代替手工计算求最短路径。而在计算机语言中迪杰斯特拉算法比较常见，简洁，故人们常借助计算机程序迪杰斯特拉算法求最短路径。这样可以广泛提高效率，容易理解。
2 需求分析
3概要设计
3.1 存储结构
一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组存储顶点信息，其中下标为i的元素存储顶点vi的信息。因此，图的邻接矩阵的存储结构定义如下: #define MVNum 50
typedef struct {
VertexType vexs[MVNum];
Adjmatrix arcs[MVNum][MVNum]；
}Mgraph;
图如下
图3.1 无向图
a b c d e f
a ∞ 3 4 ∞∞∞
b 3 ∞∞ 15 5 ∞
c 4 ∞∞ 312 ∞
d ∞ 15 3 ∞∞8
e ∞ 512 ∞∞6
f ∞∞∞8 6 ∞
图2.1 G的邻结矩阵
3.2 算法描述
(1) Dijkstra算法核心是贪心，实质是按路径长度递增产生诸顶点的最短路径算法。
迪杰斯特拉算法可用自然语言描述如下：
初始化S和D,置空最短路径终点集，置初始的最短路径值；
S[v1]=TRUE;D[v1]=0;
While(S集中的顶点数{
开始循环，每次求的v1到某个v顶点的最短路径，并将v加到S集中;
S[v]=TRUE; 更新当前最短路径及距离。
}
(2)Dijkstra算法结束后，通过设置一个数组记录下一个节点的前趋节点，然后通过倒叙的方式输出该最短路径。
(3)Dijkstra算法思想为：设G=(V,E)，G是带权无向图，V代表图中顶点集合，E代表图中含权重的边集合。将全部顶点集合V分成两组，第一组为已求出最短路径的顶点集合，用S表示（初始时S中只有一个源点，以后每求得一条最短路径，就将该路径的终点加入到集合S中）；第二组为其余待确定最短路径的顶点集合，用U表示。按最短路径长度的递增次序依次把U集合的顶点逐个加入到S集合中，约束条件是保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。算法的终止条件是集合U为空集，即集合U的顶点全部加入到集合S中。
（4）Maxint：最大整数值，表示两个不能到达的顶点。
4详细设计
4.1 功能模块图
如图4.1所示
图4.1功能模块4.2 主函数
主函数流程图如图4.2
图4.2 主函数
4.3 pd函数
函数如图4.3所示
图4.3 Pd函数
4.4 CreateMGraph函数
createMGraph函数如图4.4所示
图4.4 createMGraph函数
4.5Dijkstar函数
5程序编码
#include
#include
#define MVNum 100
#define Maxint 32767
typedef char VertexType;
typedef int Adjmatrix;
typedef enum {FALSE,TRUE}boolean;
typedef struct {
VertexType vexs[MVNum];
Adjmatrix arcs[MVNum][MVNum];
}MGraph;
int D1[MVNum],P1[MVNum];
int D[MVNum][MVNum],P[MVNum][MVNum];
int pd(MGraph *G,int &n,int &e)
{
while((n>0)&&(e>n*(n-1)/2)){
printf("你输入的顶点或边数不正确，请重新图中顶点个数和边数n，e:");
scanf("%d,%d",&n,&e);
}
return TRUE;
}
CreateMGraph(MGraph *G,int n,int e)
{
int i,j,k,w;
char a,b;
for(i=1;i<=n;i++)
