迪杰斯特拉算法实验报告(共9篇).docVIP

迪杰斯特拉算法实验报告(共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条边的边尾 边头 权值(以空格作