最短路径实验报告.doc

云南财经大学信息学院学生综合性与设计性实验报告 （ 2013—2014 学年 第 2 学期 ） 周次：第7周 日期：2014年 4 月 17 日 地点： 班级 计专13-1 学生信息 学生1 成绩 学生2 实验名称 查看“最短路径.swf”，选择熟悉的程序设计语言定义有向图，根据动画演示求取从有向图任一结点到其他结点的最短路径。 教师评语 该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□ 该同学的实验能力： A.强 □ B.中等 □ C.差 □ 该同学的实验是否达到要求： A.达到□ B.基本达到□ C.未达到□ 实验报告是否规范： A.规范□ B.基本规范□ C.不规范□ 实验过程是否详细记录： A.详细□ B.一般 □ C.没有 □ 教师签名： 年 月 日 一、实验内容与目的 1.内容 查看“最短路径.swf”，选择熟悉的程序设计语言定义有向图，根据动画演示求取从有向图任一结点 到其他结点的最短路径。 2.实验目的 了解最短路径的概论，掌握求最短路径的方法。 二、实验原理或技术路线（可使用流程图描述） 实验原理：(李燕妮负责设计，周丽琼负责编程) 图是由结点的有穷集合V和边的集合E组成，求最短路径用迪杰斯特拉算法： 1)适用条件范围： a) 单源最短路径(从源点s到其它所有顶点v); b) 有向图无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图) c) 所有边权非负(任取(i,j)∈E都有Wij≥0); 2)算法描述： a)初始化：dis[v]=maxint(v∈V,v≠s); dis[s]=0; pre[s]=s; S={s}; b)For i:=1 to n 1.取V-S中的一顶点u使得dis[u]=min{dis[v]|v∈V-S} 2.S=S+{u} 3.For V-S中每个顶点v do Relax(u,v,Wu,v) c)算法结束：dis[i]为s到i的最短距离；pre[i]为i的前驱节点 三、实验环境条件（使用的软件环境） Microsoft Visual C++6.0 实验方法、步骤（列出程序代码或操作过程） /*本程序的功能是求图中任意两点间的最短路径*/ #includestdio.h #includestdlib.h #includeconio.h #includestring.h #define ING 9999 typedef struct ArcCell{ int adj; /*顶点关系类型，用1表示相邻，0表示不相邻*/ }ArcCell,**AdjMatrix; /*邻接矩阵*/ typedef struct type{ char data[3]; /*顶点值*/ }VertexType; typedef struct{ VertexType *vexs; /*顶点向量*/ AdjMatrix arcs; /*邻接矩阵*/ int vexnum,arcnum; /*图的顶点数和边数*/ }MGraph; /*初始图*/ void InitGraph(MGraph *G) { int i,nu,mu; printf(\n输入顶点的个数和（边）弧的个数：); scanf(%d %d,nu,mu); G-arcs=(ArcCell **)malloc(nu*sizeof(ArcCell *)); for(i=0;inu;i++) /*分配邻接矩阵空间*/ G-arcs[i]=(ArcCell *)malloc(nu*sizeof(ArcCell)); G-vexs=(VertexType *)malloc(nu*sizeof(VertexType)); /*分配顶点空间*/ G-vexnum=nu;G-arcnum=mu; /*图的顶点数和边数*/ } void InsertGraph(MGraph *G,int i,VertexType e) { if(i0||iG-vexnum) return; strcpy(G-vexs[i].data,e.data); } /*确定v1在图顶点中的位置*/ int Locate(MGraph G,VertexType v1) { int i;