迪杰斯特拉算法实验报告(共9篇).doc
文本预览下载声明
迪杰斯特拉算法实验报告(共9篇)
迪杰斯特拉算法实现课程设计报告
青岛理工大学琴岛学院
课题名称：数据结构课程设计（学 院：青岛理工大学琴岛学院专业班级：学 号：学 生：指导教师：
设 计 报 告
1周）
青岛理工大学琴岛学院教务处
2012年 6月29日
篇二：数据结构课程设计报告迪杰斯特拉算法的实现
数据结构课程设计报告
迪杰斯特拉算法的实现
班级： 软件1408
学号：1130505140831
姓名： 齐瑞征
指导教师： 石锋
完成时间：2012.7.5
要求：
基于邻接矩阵存储结构，使用迪杰斯特拉算法，计算并输出指定源点到其余各顶点的最短路径及长度。
程序的输入：顶点的个数、边的个数、各个边的起点编号、终点编号和权值，源点编号。 程序输出：源点到各顶点最短路径（用顶点编号的序列表示）及长度。
例如对于教材P141 图6-16，输入数据的形式为：
顶点个数：6
边的个数：8
第1条边的起点、终点编号及权值：0,2,10
第2条边的起点、终点编号及权值：0,4,30
… …
源点编号：0
以上为程序运行时输入的数据。程序输出结果如下：
0号到1号的最短路径为：null，长度为无穷大
0号到2号的最短路径为：0,2 长度为10
… …
以上为程序输出数据。
实现过程：
1、 在VC中建立源程序，名称为：dijkstra.c，保存在工作文件夹中；
2、 在dijkstra.c中输入以下内容：
#include stdio.h
#include string.h
#include malloc.h
#include limits.h
#define MAX_NAME 5// 顶点字符串的最大长度+1
#define MAX_INFO 20// 相关信息字符串的最大长度+1
typedef int VRType;// 顶点关系的数据类型
#define INFINITY INT_MAX // 用整型最大值代替∞
#define MAX_VERTEX_NUM 20 // 最大顶点个数
typedef char InfoType; // 信息的类型
typedef char VertexType[MAX_NAME]; // 顶点数据类型及长度
typedef enum{DG, DN, AG, AN} GraphKind;
typedef struct
{
VRType adj;
InfoType *info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
AdjMatrix arcs; // 邻接矩阵
int vexnum,// 图的当前顶点数
arcnum;// 图的当前边数
GraphKind kind; // 图的种类标志
} MGraph;
#includestlib.h
#define MAX 100 //顶点最大个数
#define INFINITY 99999 //99999代表无穷大
typedef struct{
int n, e; //顶点个数，边的个数
int edges[MAX][MAX]; //存放邻接矩阵
}Mgraph;
3、 在dijkstra.c中完成如下函数，功能是从键盘接收图的数据，存放在*g中。 void Createmgraph(MGraph *G){
int i,j,k,w,IncInfo=0;
char s[MAX_INFO],*info;
VertexType va,vb;
printf(请输入顶点数, 边数:
(空格隔开)\n);
scanf(%d%d%d%*c, amp;(*G).vexnum, amp;(*G).arcnum, amp;IncInfo);
printf(请输入%d个顶点的值(%d个字符):\n, (*G).vexnum, MAX_NAME); for(i=0;i(*G).vexnum;++i) // 构造顶点向量
scanf(%s%*c,(*G).vexs[i]);
for(i=0;i(*G).vexnum;++i) // 初始化邻接矩阵
for(j=0;j(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=INFINITY; // 边的权值初始化为无穷大
(*G).arcs[i][j].info=NULL;
}
printf(请输入%d条边的边尾 边头 权值(以空格作
显示全部