综合设计型实验.docVIP

福州大学数计学院 《数据结构》上机实验报告 专业：信息数学 学号 031201206 姓名 詹小青 班级 02班 实验名称 综合设计型实验 实验内容 交通网络中的最短路径求解 实 验 目 的 和 要 求 【实验目的】 了解单源点的最短路径概念，掌握求单源点最短路径的Dijkstra算法。 【实验内容】 建立一个交通网G，利用Dijkstra算法求某个城市到其余城市的最短路径，并输出。 问 题 描 述 和 主 要 步 骤 交通网络中的最短路径求解 【实验要点及说明】 最短路径问题实际上是有向网的一种应用。单源点的最短路径问题可以描述为：对给定的网G和源点v,求v到G中其余各顶点的最短路径。 有向网G采用邻接矩阵来存储表示，另设置一个辅助数组P记录从源点到其他顶点最短路径上的顶点。D[]数组记录源点到其他顶点的长度。 实 验 结 果 （ 截 图 表 示 ） 程序： /*————————————————————————————-----------*//* */ /*用Dijkstra算法求出有向图中某个源点到其他各顶点的最短路径长度*/ /* */ /*————————————————————————————-----------*/ #include stdio.h #include malloc.h #include iostream.h #include stdlib.h #define INF 32767 #define MAXVEX 100 #define MAX 12 struct vertex { int num; //顶点编号 int data; //顶点的信息 }; //顶点类型 typedef struct graph { int n; int e; //图中顶点的个数和边的个数 struct vertex vexs[MAXVEX]; //顶点集合 int edges[MAXVEX][MAXVEX]; //边的集合 }AdjMaxix; //图的邻接矩阵类型 AdjMaxix creatmgraph() //通过用户交互产生一个有向图的邻接矩阵 { int i,j,k,w,n,e; int b,t; AdjMaxix adj; cout输入城市数:; //对图的所有信息进行逐步输入 cinn; while(nMAX||n0) { cout城市个数不正确!请重新输入!endl; cinn; } cout输入城市线路数:; cine; adj.n=n; adj.e=e; cout输入城市信息:\n; for(i=0;in;i++) { cout第i+1个城市的信息:; cinadj.vexs[i].data; adj.vexs[i].num=i; } for(i=0;in;i++) for(j=0;jn;j++) adj.edges[i][j]=0; for(k=0;ke;k++) { cout第k+1条线路:endl; cout起点:; cinb; cout终点:; cint; cout线路长度为(Km):; cinw; i=0; while(in adj.vexs[i].data!=b) i++; if(i=n) { cout输入的起点城市不存在!\n; abort(); } j=0; while(jn adj.vexs[j].data!=t) j++; if(j=n) { cout输入的终点不存在!\n; abort(); } adj.edges[i][j]=w; } return(adj); } void dispmgraph(AdjMaxix adj)//用于输出一个有向图的邻接矩阵 { int i,j,n,e; n=adj.n; e=adj.e; cout输出线路的矩阵表示:endl; cout ; for(i=-1;in;i++) printf(%6d,i); printf(\n); coutendl; for(i=0;in;i++) { printf(%6d,i); for(j=0;jn;j++) if(adj.