最短路径实验报告.doc

《最短路径实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、云南财经大学信息学院学生综合性与设计性实验报告（2013—2014学年第2学期）周次：第7周日期：2014年4月17日地点：班级计专13-1学生信息学生1成绩学生2实验名称查看“最短路径.swf”，选择熟悉的程序设计语言定义有向图，根据动画演示求取从有向图任一结点到其他结点的最短路径。教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程是否详

2、细记录：A.详细□B.一般□C.没有□教师签名：年月日一、实验内容与目的1.内容查看“最短路径.swf”，选择熟悉的程序设计语言定义有向图，根据动画演示求取从有向图任一结点到其他结点的最短路径。2.实验目的了解最短路径的概论，掌握求最短路径的方法。二、实验原理或技术路线（可使用流程图描述）实验原理：(李燕妮负责设计，周丽琼负责编程)图是由结点的有穷集合V和边的集合E组成，求最短路径用迪杰斯特拉算法：1)适用条件&范围：a)单源最短路径(从源点s到其它所有顶点v);b)有向图&无向图(无向图可以看作(u,v),(v,u)同属

3、于边集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)Fori:=1ton1.取V-S中的一顶点u使得dis[u]=min{dis[v]

4、v∈V-S}2.S=S+{u}3.ForV-S中每个顶点vdoRelax(u,v,Wu,v)c)算法结束：dis[i]为s到i的最短距离；pre[i]为i的前驱节点三、实验环境条件（使用的软件环境）MicrosoftVisualC++6.0四、实验

5、方法、步骤（列出程序代码或操作过程）/*本程序的功能是求图中任意两点间的最短路径*/#include#include#include#include#defineING9999typedefstructArcCell{intadj;/*顶点关系类型，用1表示相邻，0表示不相邻*/}ArcCell,**AdjMatrix;/*邻接矩阵*/typedefstructtype{chardata[3];/*顶点值*/}VertexType;typedefs

6、truct{VertexType*vexs;/*顶点向量*/AdjMatrixarcs;/*邻接矩阵*/intvexnum,arcnum;/*图的顶点数和边数*/}MGraph;/*初始图*/voidInitGraph(MGraph*G){inti,nu,mu;printf("输入顶点的个数和（边）弧的个数：");scanf("%d%d",&nu,&mu);G->arcs=(ArcCell**)malloc(nu*sizeof(ArcCell*));for(i=0;iarc

7、s[i]=(ArcCell*)malloc(nu*sizeof(ArcCell));G->vexs=(VertexType*)malloc(nu*sizeof(VertexType));/*分配顶点空间*/G->vexnum=nu;G->arcnum=mu;/*图的顶点数和边数*/}voidInsertGraph(MGraph*G,inti,VertexTypee){if(i<0

8、

9、i>G->vexnum)return;strcpy(G->vexs[i].data,e.data);}/*确定v1在图顶点中的位置*/intL

10、ocate(MGraphG,VertexTypev1){inti;for(i=0;ivexnum*sizeof(int));for(i=0;i<10;i++)p[i]=0;for(i=0;iv

11、exnum;++i)/*初始邻接表*/{for(j=0;jvexnum;++j)G->arcs[i][j].adj=ING;}for(k=0;karcnum;++k){printf("输入第%d条（边）弧相对的两个顶点值:",k+1);scanf("%s%s",v1.data,v