最短路径实验报告.doc

云南财经大学信息学院学生综合性与设计性实验报告（ 20132014 学年 第 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都有Wij0);2)算法描述：a)初始化：disv=maxint(vV,vs); diss=0; pres=s; S=s;b)For i:=1 to n1.取V-S中的一顶点u使得disu=mindisv|vV-S2.S=S+u3.For V-S中每个顶点v do Relax(u,v,Wu,v)c)算法结束：disi为s到i的最短距离；prei为i的前驱节点三、实验环境条件（使用的软件环境）Microsoft Visual C+6.04、 实验方法、步骤（列出程序代码或操作过程）/*本程序的功能是求图中任意两点间的最短路径*/#include #include #include #include #define ING 9999 typedef struct ArcCell int adj; /*顶点关系类型，用1表示相邻，0表示不相邻*/ ArcCell,*AdjMatrix; /*邻接矩阵*/ typedef struct type char data3; /*顶点值*/ 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;iarcsi=(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(iG-vexnum) return; strcpy(G-vexsi.data,e.data); /*确定v1在图顶点中的位置*/ int Locate(MGraph G,VertexType v1) int i; for(i=0;ivexnum*sizeof(int); for(i=0;i10;i+) pi=0; for(i=0;ivexnum;+i) /*初始邻接表*/ for(j=0;jvexnum;+j) G-arcsij.adj=ING; for(k=0;karcnum;+k) printf(n输入第%d 条（边）弧相对的两个顶点值:n,k+1); scanf(%s %s,v1.data,v2.data); /*输入相邻的两个点值*/ printf(输入它们的权值: ); scanf(%d,&w); i=Locate(*G,v1);j=Locate(*G,v2); /*用i 和j来确定它们的位置*/ G-arcsij.adj=w; /*输出邻接矩阵*/ void Pint(MGraph G) int i,j; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) if(G.arcsij.adj!=ING) printf(t%d,G.arcsij.adj); else if(i=j)printf(t0); else printf(t); printf(n); /*对顶点V0到其余顶点v的最短路径pv及其带权长度Dv若pvw为1，则w是从V0到W当前求得最短路径上的顶点, finalv为1，当且仅当v属于S，即已经求得从v0到v的最短路*/ void ShortestPath(MGraph G,int v0,int *p,int *D) int v,u,i,w,min; int *final; final=(int *)malloc(G.vexnum*sizeof(int); /*分配空间*/ for(v=0;vG.vexnum;+v) finalv=0;Dv=G.arcsv0v.adj; /*初始化*/ for(w=0;wG.vexnum;+w) pvw=0; /*设空路径*/ if(DvING)pvv0=1;pvv=1; /*v到v0有路径*/ Dv0=0;finalv0=1; /*初始化，V0顶点属于S集*/ for(i=1;iG.vexnum;i+) /*其余G.vexnum-1个顶点*/ min=ING; for(w=0;wG.vexnum;+w) /*求出矩阵这一行的最小值*/ if(!finalw) /*W顶点属于V-S中*/ if(Dwmin)v=w;min=Dw; finalv=1; /*离V0顶点最近的V加入S集*/ for(w=0;wG.vexnum;+w) /*更新当前最短路径及距离*/ if(!finalw&(min+G.arcsvw.adjDw) /*不是最小的，修改Dw,Pw*/ Dw=min+G.arcsvw.adj; for(u=0;uG.vexnum;u+) pwu=pvu; pww=1; free(final); void main() MGraph G; VertexType e; int i,j; int *p; int *D; InitGraph(&G); p=(int *)malloc(G.vexnum*sizeof(int *); for(i=0;iG.vexnum;i+) pi=(int *)malloc(G.vexnum*sizeof(int); D=(int *)malloc(G.vexnum*sizeof(int); printf(顶点值：n); for(i=0;iG.vexnum;+i) /*给图顶点向量付值*/ scanf(%s,e.data);InsertGraph(&G,i,e); CreateUND(&G); /*构造图结构*/ printf(邻接矩阵为：n); Pint(G); for(i=0;iG.vexnum;i+) /*输出邻接矩阵*/ ShortestPath(G,i,p,D); /*调用最短函数*/ for(j=0;jG.vexnum;j+) if(i!=j) printf( %s 到%s 的最短路径为%d n,G.vexsi.data,G.vexsj.data,Dj); printf(nn); getch(); 五、实验过程原始记录( 测试数据、图表)请给出各个操作步骤的截图和说明，要求有对时间复杂度和空间复杂度的说明。（共同负责）