数据结构课程设计最短路径问题实验报告

青岛理工大学琴岛学院设计报告课题名称：求解最优交通路径学院：计算机工程系专业班级：计算机科学与技术学号：#######学生：**指导教师：**青岛理工大学琴岛学院教务处2011 年 7 月 7日图1B.具体功能实现及相应的弗洛伊德算法首先,建立查询信息对话框，使用户能够录入需要查询的城市代号，并显示路径长度及最短路径沿途经过的城市。

并相应地添加如下变量int m_v0;int m_v1;int m_lj;CString m_zd;具体代码如下：#define MAXV 25 //最大顶点个数#define INF 32767 //用32767表示∞//以下定义邻接矩阵类型typedef struct{ int no; //顶点编号char name[10]; //顶点名称} VertexType; //顶点类型typedef struct //图的定义{ int edges[MAXV][MAXV]; //邻接矩阵int vexnum,arcnum; //顶点数，弧数VertexType vexs[MAXV]; //存放顶点信息} MGraph; //图的邻接矩阵类型1.通过函数CreatUDN()存放城市路径信息，输入顶点之间的路径长度，创建带权图的邻接矩阵。

void CTDialog::CreatUDN(){MGraph *g=(MGraph*)malloc(sizeof(MGraph));int i,j;for(i=0;i<MAXV;i++) //录入权值，计算存储用for(j=0;j<MAXV;j++){g->edges[i][j]=INF;if(i==j)g->edges[i][j]=0; //初始化置任意两城市之间距离为无穷大，即两城市之间没有直接通路{if(i!=j)m_zd="没有路径";}else if(x==i&&y==j){m_lj=A[i][j];CString zfc;zfc.Format("%d",i); //输出路径上的起点m_zd+=zfc;ppath(path,i,j); //输出路径上的中间点zfc.Format("-->%d",j); //输出路径上的终点m_zd+=zfc;}}}4.输出最短路径函数，递归输出从顶点i到j的最短路径中依次经过的顶点，直到path[i][j]=-1，即没有中间顶点为止。

青岛理工大学琴岛学院
设计报告
课题名称：数据结构课程设计
学院：计算机工程系
专业班级：计算机网络技术
学号：aaaaaa
学生： aaa
指导教师： aaaaaaa
青岛理工大学琴岛学院教务处
2011 年 12 月 18日
四．调试分析（调试过程中出现的问题及处理方式）调试出现的界面
1)进入程序弹出查询信息对话框如图2：
图2
2) 输入查询信息，显示路径长度及最短路径，如果输入代号不在0~24之内，提示出错。

图3
图4
B．出现的问题及解决方式
1、在执行程序的时候不能显示最短的距离
解决方法：增加一个函数调用，调用的函数为ShortestPath(v0); /*计算两个城市之间的最短路径*/
2、不能连续查询，即查询一次完成后，必须重新运行才能就进行二次查询
解决方法：在代码中添加while( ) 语句printf("是否继续，1（继续查询），0（退出查询）");
printf("\n"); scanf("%d",&ch); 详见图5
图 5。

数据结构实验报告五最短路径应用所学数据结构知识，独立完成问题分析^p ，结合数据结构理论知识，编写程序求解指定问题。

1.3 系统实现方案首先确定系统要实现怎样的目的，实现这些目的需要先实现哪些程序，这就是核心部分，划分出模块并写出其代码，此程序大致分了六大模块，由一个主函数组和五个自定义函数组成，而后是上机调试，将几大模块组成一个协调完整的能实现其功能的程序，最后提交设计报告二、系统分析^p ：2.1设计思想用邻接矩阵来存储交通网络图的信息，运用迪杰斯特拉算法实现图上单最短路径问题，然后运用费洛伊德算法实现图中任意一对顶点间最短路径问题，这样就会实现旅客所要咨询的问题。

2.2设计要求该交通咨询系统要完成城市网络图的存储，并要实现求任意一个城市顶点到其他城市顶点的最短路径问题，还要实现任意两个城市顶点间的最短路径问题。

故设计要分成三部分，一是建立交通网络图的存储结构；二是解决单路径问题；最后再实现两个城市之间的最短路径问题。

设计要求：1.建立交通网络网的存储结构。

2.总体设计要画流程图。

3.提供程序测试方案。

4.界面友好。

2.3需求分析^p根据要求，需要在系统中建立无向图。

系统应该有高度灵活性，可以由用户根据当前交通网络图输入初始数据，并且可以更改。

系统根据用户的输入建立无向图的结构，并通过狄克斯特拉算法和弗洛伊德算法实现要求，并提供两种功能供用户选择。

2.4 算法描述录入城市及道路数据预置城市间的距离构建交通网交通查询系统根据无向图建立查询功能查询一个城市到其它城市的最短路径查询任意两城市间的最短路径狄克斯特拉算法的具体流程图开始初始化距离和路径 i=1 i++ j=1;j++;jn 修改最短路径和距离输出结果弗洛伊德算法的具体流程图开始初始化距离和路径设为从到的只以集合中的节点为中间节点的最短路径的长度最短路径不经过点k 最短路径经过点k 输出结果三、概要设计：程序中将涉及下列两个抽象数据类型：一个是图，一个是队列。

数据结构与算法课程设计报告书题目：导航最短路径查询班级：11101111学号：**********姓名：教师周期：2012.12.17-2012.12.21 （以下由验收教师填写）成绩：2012年12月21日《导航最短路径查询》一、课程设计的目的与要求（一）课程设计目的与任务通过学习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、编码集成以及调试分析，熟练掌握数据结构的选择、设计、实现、以及操作方法，为进一步的开发应用打好基础。

（二）题目要求要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。

同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

二、设计正文1、系统分析和开发背景该程序所做的工作是给司机们提供最佳路线，来提高能源和时间的合理利用。

（1）把城市交通线路转化为图，从而对图进行相应的结构存储；（2）程序的输出信息主要为：起始城市到目的城市的最短路路径。

（3）程序的功能主要包括：城市之间路径的存储，最短路径的计算，以及最短路径和邻接矩阵的输出；2 、功能详细描述先假设有四个城市甲乙丙丁，甲乙相距2千米，且只有从乙到甲的单程线路。

甲丙相距7千米，且只有从甲到丙的单程线路。

甲丁相距4千米，且只有从甲到丁的单程线路。

乙丙相距5千米，且只有从丙到乙的单程线路。

乙丁相距3千米，且只有从丁到乙的单程线路。

丙丁相距3千米，且只有从丁到丙的单程线路。

戊甲相距6千米，且只有从戊到甲的单程线路。

戊丁相距2千米，且只有从丁到戊的单程线路。

乙己相距8千米，且只有从乙到己的单程线路。

丙己相距6千米，且只有从己到丙单程线路。

编程出能求出个一点到任一点的最短路经。

3、数据结构设计（1）typedef struct{int no; //顶点编号InfoType info; //顶点其他信息，这里用于存放边的权值}VertexType; //顶点类型typedef struct //图的定义{int edges[MAXV][MAXV]; //邻接矩阵int n,e; //顶点数，弧数VertexType vexs[MAXV]; //存放顶点信息}MGraph; //图的邻接矩阵类型//以下定义邻接表类型typedef struct ANode //弧的结点结构类型{int adjvex; //该弧的终点位置struct ANode *nextarc; //指向下一个弧的指针InfoType info; //该弧的相关信息，这里用于存放权值}ArcNode;typedef int Vertex;typedef struct Vnode //邻接表头结点的类型{Vertex data; //顶点信息ArcNode *firstarc[MAXV]; //指向第一条弧}VNode;typedef VNode AdjList[MAXV];//AdjList是邻接表类型typedef struct{AdjList adjlist; //邻接表int n,e; //图中顶点数n和边数e}ALGraph; //图的邻接表类型4、主要功能逻辑过程和实现算法用到的主要函数：（1）void DispMat(MGraph g) //输出邻接矩阵（2）void ppath(int path[][MAXV],int v,int endv) //输出相应选择的起点和终点的最短路。

最短距离问题数据结构课程设计报告数据结构课程设计报告题⽬：北海公园主要游览景点之间最短距离问题⼀、课程设计题⽬：北海公园主要游览景点之间最短距离问题⼆、问题定义：（由教师指定）图的最短路径问题是指从指定的某⼀点v开始，求得从该地点到图中其它各地点的最短路径。

并且给出求得的最短路径的长度及途径的地点。

除了完成最短路径的求解外，还能对该图进⾏修改，如顶点以及边的增删、边上权值的修改等。

三、需求分析1、设计北海公园的平⾯图。

选取若⼲个有代表性的景点抽象成⼀个⽆向带权图，以图中顶点表⽰公园内各景点，边上的权值表⽰两景点之间的距离。

2、输⼊的形式：整型数字输⼊值的范围：0-103、输出的形式：由⼆元组表⽰以邻接矩阵存储的图4、程序所能达到的功能；（1）输出顶点信息：将公园内各景点输出。

（2）输出边的信息：将公园内每两个位置的距离输出。

（3）修改：修改两个位置的距离，并重新输出每两个位置的距离；（4）求最短路径：输出给定两点之间的最短路径的长度及途经的地点，输出任意⼀点与其他各点的最短路径。

（5）删除：删除任意⼀条边。

（6）插⼊：插⼊任意⼀条边。

5、算法涉及的基本理论分析：定义邻接矩阵adjmatrix；⾃定义顶点结构体V ertexType；定义邻接表中的边结点类型edgenode；switch算法；狄克斯特拉法（Dijkstra）求任意两结点之间的最短路径；6、题⽬研究和实现的价值。

四、算法设计1、概要设计（1）存储结构设计本系统采⽤图结构类型存储抽象北海公园地图的信息。

其中：各景点间的邻接关系⽤图的邻接矩阵类型（adjmatrix）存储；景点（顶点）信息⽤结构数组（V ertexType）存储，其中每个数组元素是⼀个结构变量，包含景点编号、景点名称两个分量；图的顶点个数由分量MaxV ertexNum表⽰，它是整型数据。

（2）主界⾯设计为了实现公园导游系统各功能的管理，⾸先设计⼀个含有多个菜单项的主控菜单⼦程序以链接系统的各项⼦功能，⽅便⽤户使⽤本系统。

最短路径_数据结构课程设计报告第一篇：最短路径_数据结构课程设计报告数据结构课程设计《数据结构》课程设计报告设计题目：____医院选址____________ 姓名：__________________ 学号：________________ 专业：___________院系：____________班级：_________________ 指导教师：_________________年 1月 3 日数据结构课程设计一、问题描述(1)题目内容：有n个村庄，现要从这n个村庄中选择一个村庄新建一所医院，使其余的村庄到这所医院的距离总和来说较短。

（n>=5）(2)基本要求：(3)可以输出每一对点间的路径长度；然后选取偏心度，最小的偏心度即为所求。

二、需求分析(4)本程序的功能包括找出每一对点间的路径长度。

(5)然后算出每一对点的偏心度。

(6)其中最小的偏心度即为所求。

三、概要设计操作集合：(7)public:MGraph(DataType a[],int b[][MaxSize],int n,int e);//初始化邻接矩阵和路径(8)void Floyd();//弗洛伊德算法的实现(9)void getE();//获取偏心度(10)void showdist();//把每一对顶点之间的路径权值show出来(11)~MGraph(){} //类的析构函数四、数据结构设计(1)DataType vertex[MaxSize];//存放图中顶点的数组(2)intarc[MaxSize][MaxSize];//存放图中边的数组(3)string path[MaxSize][MaxSize];//存放从Vi到Vj的最短路径，初始为//path[i][j]=“ViVj”(4)int dist[MaxSize][MaxSize];//存放求得的最短路径长度(5)int vertexNum, arcNum;//图的顶点数和边数(6)int E[MaxSize][2];//获取最小偏心度和该顶点五、算法设计1.算法分析1）对带权有向图的，调用Floyd算法，对每一对顶点间的最短路径长度的矩阵；2）对最短路径长度矩阵的每列求最大值，即得到各点的偏心度；3)具有最小偏心度的顶点即为所求。

实验报告课程名：数据结构（C语言版）实验名：迷宫问题II姓名：班级：学号：撰写时间：2014/10/10一实验目的与要求1. 了解栈的应用2. 利用栈在迷宫中找到一条路二实验内容•一个迷宫如图1所示, 是由若干个方格构成的一个矩形, 其中有唯一的一个入口(用⃝标示), 有唯一的一个出口(用△标示). 图中深色的方格无法到达, 浅色的方格都是可以到达的. 每一次只能从当前方格前进到与当前方格有公共边的方格中(因此前进方向最多有四个).•本次实验的迷宫问题要求找到从入口到出口的最短的路.图1：迷宫三实验结果与分析程序：#include <stdio.h>#include <stdlib.h>int Maze(int ox,int oy,int ex,int ey,int rnum,int cnum,int a[rnum][cnum]){int b[rnum][cnum];int i,j,Znum=0;for(i=0;i<rnum;++i){for(j=0;j<cnum;++j){b[i][j]=a[i][j];if(a[i][j]==0){Znum=Znum+1;}}}int Qx[Znum+1], Qy[Znum+1], P[Znum+1], head=0, tail=0; for(i=0;i<Znum+1;++i){Qx[i]=-10;Qy[i]=-10;P[i]=-10;}/*int dx[4] = {0,1,0,-1};int dy[4] = {-1,0,1,0};int neighbor_num = 4;*/int dx[8] = {-1, 0, 1,1,1,0,-1,-1};int dy[8] = {-1,-1,-1,0,1,1, 1, 0};int neighbor_num = 8;if(ox==ex && oy==ey){printf("(%d,%d)",ox,oy);}else{Qx[tail]=ox;Qy[tail]=oy;P[tail]=-1;++tail;b[ox][oy]=2;}int brand = -1;while(tail>head){for(i=0;i<neighbor_num;i++){int tx = Qx[head]+dx[i];int ty = Qy[head]+dy[i];if(b[tx][ty]==0){if(tx==ex && ty==ey){printf("(%d,%d), ",tx,ty);int t = head;while(t>=0){printf("(%d,%d), ",Qx[t],Qy[t]);t=P[t];}head=tail;brand=1;break;}else{Qx[tail]=tx;Qy[tail]=ty;P[tail]=head;++tail;b[tx][ty]=2;}}}++head;}return(brand);}int main(int argc, char *argv[]) {int rnum = 10;int cnum = 10;int a[10][10]={{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}};//假设外面有一层不可到达的方块，故迷宫成了10乘10型int ox=1,oy=1,ex=rnum-2,ey=cnum-2;int brand = Maze(ox,oy,ex,ey,rnum,cnum,a);if(brand<0){printf("There is no way\n");}return 0;}图1：实验结果截图。

问题描述：若用有向网表示某地区的公路交通网，其中顶点表示该地区的一些主要场所，弧表示已有的公交线路，弧上的权表示票价。

试设计一个交通咨询系统，指导乘客以最少花费从该地区中的某一场所到达另一场所。

基本要求：（1）从文件中读入有向网中顶点的数量和顶点间的票价的矩阵。

（2）以用户指定的起点和终点，输出从起点到终点的花费。

一、需求分析：1、本程序需要用矩阵来存储图的各种信息。

2、测试数据输入（文件）5－1 10 3 20 －1－1 －1 －1 5 －1－1 2 －1 －1 15－1 －1 －1 －1 11－1 －1 －1 －1 －1（用户）起点 0终点 4输出18实现提示：（1）设图的顶点大于1个，不超过30个，每个顶点用一个编号表示（如果一个图有n个顶点，则它们的编号分别为0, 1, 2, 3, …, n-1）。

（2）此题为求有向网中顶点间最短路径问题，可建立以票价为权的邻接矩阵，用Dijkstra算法求最短路径长度。

（3） Dijkstra算法中有一个辅助向量D，表示当前所找到的从源点到其它点的最短路径长度。

因为每次都要在D中找最小值，为提高性能，用最小值堆的优先队列存储D值。

（4）考虑没有路径时的输出。

二、概要设计：抽象数据类型：为实现上述功能需建立一个二维数组和图类。

算法的基本思想：1、图的信息的读取：定义一个二维数组，将图的信息读入，并将两边距离为-1的边转换为一个较大的数（>>途中各点之间的距离）。

2、Dijkstra算法：根据输入的第一个结点首先找到（直接距离）该点最近的A，则这两点之间的边是必须的，然后比较通过A到其他点的距离l1和直接到其他点的距离l2。

如果l1<l2，则用l1的距离替换l2。

重复上述操作n-1（n为结点数）次。

得到的即为第一个结点到其他结点的最短距离。

程序的流程程序由三个模块组成：输入模块：读入图的信息（用矩阵进行存储）。

处理模块：Dijkstra算法。

HUNAN UNIVERSITY 课程实习报告题目最短路径问题学生姓名学生学号专业年级指导老师完成日期一、需求分析本实验是求最短路径的问题，从文件中读入有向网中顶点的数量和顶点间的票价的矩阵，以用户指定的起点，在文件中输出到其余各顶点的最短路径及花费。

（1）输入：输入的形式：（文件）5-1 10 3 20 -1-1 -1 -1 5 -1-1 2 -1 -1 15-1 -1 -1 -1 11-1 -1 -1 -1 -1（用户）输入起点：0输入值的范围：文件输入中，顶点数和矩阵中顶点间的票价均为整型int，用户输入中，起点数为整型int。

（2）输出的形式：（文件）源点0到顶点1的最小花费为:5路径为：0——>2——>1源点0到顶点2的最小花费为:3路径为：0——>2源点0到顶点3的最小花费为:10路径为：0——>2——>1——>3源点0到顶点4的最小花费为:18路径为：0——>2——>4（3）程序所达到的功能：在文件中给出有向网的顶点个数和顶点间的票价的矩阵，以用户指定的起点，在文件中输出起点到其余各顶点的最短路径及花费。

（4）测试数据：a.输入：（文件）5-1 10 3 20 -1-1 -1 -1 5 -1-1 2 -1 -1 15-1 -1 -1 -1 11-1 -1 -1 -1 -1（用户）输入起点：0输出：（文件）源点0到顶点1的最小花费为:5路径为：0——>2——>1源点0到顶点2的最小花费为:3路径为：0——>2源点0到顶点3的最小花费为:10路径为：0——>2——>1——>3源点0到顶点4的最小花费为:18路径为：0——>2——>4b.输入：（文件）5-1 10 3 20 -1-1 -1 -1 5 -1-1 2 -1 -1 15-1 -1 -1 -1 11-1 -1 -1 -1 -1（用户）输入起点：2输出：（文件）源点2到顶点0：没有连通路径源点2到顶点1的最小花费为:2路径为：2——>1源点2到顶点3的最小花费为:7路径为：2——>1——>3源点2到顶点4的最小花费为:15路径为：2——>4c.输入：（文件）618 10 3 20 -1 915 -1 -1 5 -1 -1-1 20 16 -1 -1 15-1 -1 30 -1 6 32 9 -1 20 -1 -1-1 8 12 -1 -1 5（用户）输入起点：5输出：（文件）源点5到顶点0的最小花费为:21路径为：5——>1——>3——>4——>0源点5到顶点1的最小花费为:8路径为：5——>1源点5到顶点2的最小花费为:12路径为：5——>2源点5到顶点3的最小花费为:13路径为：5——>1——>3源点5到顶点4的最小花费为:19路径为：5——>1——>3——>4d.输入：（文件）618 10 3 20 -1 915 -1 -1 5 -1 -1-1 20 16 -1 -1 15-1 -1 30 -1 6 32 9 -1 20 -1 -1-1 8 12 -1 -1 5（用户）输入起点：3输出：（文件）源点3到顶点0的最小花费为:8路径为：3——>4——>0源点3到顶点1的最小花费为:11路径为：3——>5——>1源点3到顶点2的最小花费为:11路径为：3——>4——>0——>2源点3到顶点4的最小花费为:6路径为：3——>4源点3到顶点5的最小花费为:3路径为：3——>5e.输入：（文件）3-1 -1 -1-1 -1 -1-1 -1 -1（用户）输入起点：1输出：（文件）源点1到顶点0：没有连通路径源点1到顶点2：没有连通路径f.输入：（文件）3-1 -1 -1-1 -1 -1-1 -1 -1（用户）输入起点：3输出：（文件）源点3到顶点0的最小花费为:-572562307路径为：3——>1——>0源点3到顶点1的最小花费为:-572662307路径为：3——>1源点3到顶点2的最小花费为:-572662307路径为：3——>2二、概要设计（1）所有抽象数据类型的定义：const int MaxNum=100000;//利用邻接矩阵存储图：class Graph{private:int *Adj;//保存邻接矩阵的一维数组j和k之间权值存储在Adj[j*Num+k]中int Num;public:Graph();~Graph();void Floyd(int start);};（2）算法的基本思想：采用邻接矩阵为图的存储结构，保存邻接矩阵的一维数组j和k之间权值存储Adj[j*Num+k]中，以用户指定的起点，进行弗洛伊德算法，先初始化最短路径，对角线元素设置为0，其他元素设置为边的权值，没有有向边设置为MaxNum，依次插入中间点k，判断是否检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，若不成立则路径不改变，若成立则更新最短路径，设置Dis(i,j) = Dis(i,k) + Dis(k,j)，直至循环结束，更新后的最短路径入栈，在文件中输出到其余各顶点的最短路径及花费。

实验报告实验名称最短路径课程名称数据结构与算法实验||专业班级：信息安全学号：姓名：实验六最短路径一、实验目的1.学习掌握图的存储结构2.学会编写求最短路径的算法二、实验内容1、实验题目编写代码实现Dijkstra生成最短路径的算法，其中要有完整的图的输入输出2、简单介绍图的存储：用邻接矩阵，这样会方便不少。

邻接矩阵是一个二维数组，数组中的元素是边的权（一些数值），数组下标号为结点的标号。

（1）例如二维数组中的一个元素M[5][6]的值为39，则表示结点5、6连接，且其上的权值为39。

（2）用邻接矩阵存储图，对图的读写就简单了。

因为邻接矩阵就是一个二维数组，因此对图的读写就是对二维数组的操作。

只要能弄清楚边的编号，就能把图读入了。

用一对结点表示边（也就是输入的时候输入一对结点的编号）求最短路径的算法：求最短路径就是求图中的每一个点到图中某一个给定点（这里认为是编号为0的点）的最短距离。

具体算法就是初始有一个旧图，一个新图。

开始的时候旧图中有所有的结点，新图中初始为只有一个结点（源点，路径的源头）。

整个算法就是不停的从旧图中往新图中添加点，直到所有的点都添加到新图中为止。

要实现这个算法，除了用二维数组保存图，还需要使用到两个辅助的数组数组find[N]：此数组是用来表示标号对应的结点是否已经被添加到新图中（因为只有旧图中的点我们才需要添加到新图中，并且只有旧图中点到源点的距离，我们才需要进行更新）其中N为图中结点的个数。

数组distance[N]：此数组记录图中的点到源点的距离。

这个数组里面存放的值是不断进行更新的。

其中N为图中结点的个数。

3、程序简单模板只是参考，不需要照着这个来写//最短路径#ifndef MYGRAPH_H_#define MYGRAPH_H_class MyGraph{public:void readDirectedGraph();MyGraph(int size);//构造函数中设置图的大小，分配空间void writeGraph();void shortPath(int source);//求最短路径protected:private:int **m_graph;//用二维数组保存图int m_size;//图的大小};#endif///////////////////////////////////////////// //////////////////////////构造函数中设置图的大小，分配空间MyGraph::MyGraph(int size){int i,j;m_size=size;//给图分配空间m_graph=new int* [m_size];for (i=0;i<m_size;i++){m_graph[i]=new int[m_size];}for (i=0;i<m_size;i++){for(j=0;j<m_size;j++){m_graph[i][j]=INT_MAX;}}}三、实验代码#include<iostream>#include <iomanip>#include <stack>#include <deque>#include <fstream>using namespace std;struct primnode{public:char begvex;char endvex;int lowcost;};struct adknode{int dist;//最近距离char way[50];//顶点数组int nodenum;//经过的顶点数};class Mgraph//邻接矩阵储存结构{public:Mgraph(){}~Mgraph(){}void CreatMGraph();void DFS (int );//用递归实现void DFS1(int );//非递归void BFS(int );void print();void prim();int mini();int low();//最短距离函数的辅助函数int LocateVex(char);void kruskal();void Dijkstra();void Floyd();private:int number;//顶点数目int arcnum;//边的数目char vexs[50];int arcs[50][50];int visited[50];//便利时的辅助工具primnode closeedge[50];//primadknode dist[50];//最短路径int D[20][20];//floyd算法距离int P[20][20][20];//floyd算法路径};int Mgraph::LocateVex(char s){for(int i=0;i<number;i++)if (vexs[i]==s)return i;return -1;}void Mgraph::print(){cout<<"顶点为：";for(int k=0;k<number;k++)cout<<vexs[k];cout<<endl;for(int i=0;i<number;i++){for(int j=0;j<number;j++)cout<<setw(6)<<left<<arcs[i][j]<<" ";cout<<endl;}for(int m=0;m<number;m++)cout<<visited[m];cout<<endl;}void Mgraph::CreatMGraph()//图的邻接矩阵储存结构{char vex1,vex2;int i,j,k,m;cout<<"请输入定点数，边数："<<endl;cin>>number>>arcnum;cout<<"请输入顶点（字符串类型）："<<endl;for(i=0;i<number;i++)cin>>vexs[i];for(i=0;i<number;i++)for(j=0;j<number;j++)arcs[i][j]=1000;for(k=0;k<arcnum;k++){cout<<"请输入边的两个顶点及边的权值："<<endl; cin>>vex1>>vex2>>m;i=LocateVex(vex1);j=LocateVex(vex2);arcs[i][j]=m;arcs[j][i]=m;}}void Mgraph::DFS(int i=0)//用递归实现{int j;cout<<vexs[i]<<"------>";visited[i]=1;for (j=0;j<number;j++){if(!(arcs[i][j]==1000)&&!visited[j])DFS(j);}}void Mgraph::DFS1(int i=0)//非递归{stack<int> st;st.push(i);while(!st.empty()){int j=st.top();st.pop();cout<<vexs[j]<<"---->";visited[j]=1;for(int k=0;k<number;k++){if((!(arcs[j][k]==1000))&&!visited[k])st.push(k);}}}void Mgraph::BFS(int i=0)//广度优先遍历{deque<int> de;de.push_back(i);cout<<vexs[i]<<"------>";visited[i]=1;while(!de.empty()){int k=de.front();for(int j=0;j<number;j++){if(arcs[k][j]!=1000&&!visited[j]){cout<<vexs[j]<<"------>";visited[j]=1;de.push_back(j);}}de.pop_front();}}int Mgraph::mini(){static int i;int min=0;for (int j=0;j<number;j++){if(!visited[j]){if (closeedge[min].lowcost>closeedge[j].lowcost){min=j;}}}i=min;cout<<"包括边("<<closeedge[i].begvex<<","<<closeedge[i].endvex<<")"; return i;}void Mgraph::prim(){char u;cout<<"请输入起始顶点："<<endl;cin>>u;int i=LocateVex(u);visited[i]=1;for(int j=0;j<number;j++){closeedge[j].begvex=u;closeedge[j].endvex=vexs[j]; closeedge[j].lowcost=arcs[i][j];}for (int m=1;m<number;m++){int n=mini();visited[n]=1;closeedge[n].lowcost=1000;for (int p=0;p<number;p++){if(!visited[p]){if(arcs[p][n]<closeedge[p].lowcost){closeedge[p].lowcost=arcs[p][n];closeedge[p].begvex=vexs[n];}}}}}void Mgraph::kruskal(){int a,b,k=0;int min=1000;int arcs1[20][20];for (int m=0;m<number;m++)visited[m]=m;//每一个顶点属于一颗树for (int i=0;i<number;i++)for(int j=0;j<number;j++)arcs1[i][j]=arcs[i][j];while (k<number-1){min=1000;for (int i=0;i<number;i++){for (int j=0;j<number;j++){if (arcs1[i][j]<min){a=i;b=j;min=arcs1[i][j];}}}if (visited[a]!=visited[b]){cout<<"包括边("<<vexs[a]<<","<<vexs[b]<<")";k++;for (int n=0;n<number;n++){if (visited[n]==visited[b])visited[n]=visited[a];}}elsearcs1[a][b]=arcs[b][a]=1000;}}void Mgraph::Dijkstra(){cout<<"请输入起始点"<<endl;char u;cin>>u;int i=LocateVex(u);visited[i]=1;for (int j=0;j<number;j++){dist[j].dist=arcs[i][j];dist[j].nodenum=0;}for (j=1;j<number;j++){int distance=1000;int min=0;for (int n=0;n<number;n++){if(!visited[n]){if (distance>dist[n].dist){distance=dist[n].dist;min=n;}}}int m=min;visited[m]=1;for (n=0;n<number;n++){if(!visited[n]){if((dist[m].dist+arcs[m][n])<dist[n].dist){dist[n].dist=dist[m].dist+arcs[m][n];dist[n].nodenum=0;for (int x=0;x<dist[m].nodenum;x++){dist[n].way[x]=dist[m].way[x];dist[n].nodenum++;}dist[n].way[dist[n].nodenum++]=vexs[m];} } } }//输出功能for (int n=0;n<number;n++){if (n!=i){ if(dist[n].dist<1000){cout<<vexs[i]<<"到"<<vexs[n]<<"的最近距离为："<<dist[n].dist<<endl;cout<<"经过的顶点为："<<vexs[i]<<"---->";for (int p=0;p<dist[n].nodenum;p++){ cout<<dist[n].way[p]<<"----->";}cout<<vexs[n]<<endl;}elsecout<<vexs[i]<<"到"<<vexs[n]<<"没有通路"<<endl;} } }void Mgraph::Floyd(){int i,j,m,n;for ( i=0;i<number;i++)for ( j=0;j<number;j++)for (m=0;m<number;m++)P[i][j][m]=0;for ( i=0;i<number;i++)for ( j=0;j<number;j++){D[i][j]=arcs[i][j];if(D[i][j]<1000){P[i][j][i]=1;P[i][j][j]=1;} }for ( i=0;i<number;i++)for ( j=0;j<number;j++)for (m=0;m<number;m++){if (i==j||j==m||i==m)continue;if (D[i][m]+D[m][j]<D[i][j]){D[i][j]=D[i][m]+D[m][j];for (n=0;n<number;n++){P[i][j][n]=P[i][m][n]||P[m][j][n];} } }for ( i=0;i<number;i++)for ( j=0;j<number;j++){if (D[i][j]<1000){cout<<vexs[i]<<"到"<<vexs[j]<<"的最近距离为："<<D[i][j]<<endl;cout<<"经过的顶点为：";for (m=0;m<number;m++){if (P[i][j][m]){cout<<vexs[m]<<"------>";} }cout<<endl;}elseif (i!=j)cout<<vexs[i]<<"到"<<vexs[j]<<"没有通路"<<endl;}}int main(){Mgraph g;g.CreatMGraph();g.Floyd();return 0;}四、实验结果五、实验总结本次实验主要是学习掌握图的存储结构，学会编写求最短路径的算法。

《求最短路径的实验报告》1.需解决的的问题创建一个网的存储结构，并求最短路径2.数据结构的定义typedef struct{VertexType vexs[MVNum]; //顶点数组，类型假定为char型Adjmatrix arcs[MVNum][MVNum]; //邻接矩阵，类型假定为int型}MGraph;int D1[MVNum],P1[MVNum];int D[MVNum][MVNum],P[MVNum][MVNum];3.程序的结构图4.函数的功能（1）迪杰斯特拉算法void Dijkstra(MGraph *G,int v1,int n){ //用迪杰斯特拉算法求有向图G的v1顶点到其他顶点v的最短路径P[v]和其权D[v] //设G是有向图的邻接矩阵，若边<i,j>不存在，则G[i][j]=Maxint//S[v]为真当且仅当v在S中int D2[MVNum],P2[MVNum];int v,i,w,min;enum boolean S[MVNum];for(v=1;v<=n;v++){//初始化S和DS[v]=FALSE; //设置最短路径终点集D2[v]=G->arcs[v1][v]; //设置初始的最短路径值if(D2[v]<Maxint)P2[v]=v1; //v1是v的前驱elseP2[v]=0; //v无前驱}D2[v1]=0;S[v1]=TURE; //S集初始时只有源点，源点到其自身的距离为0//开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中for(i=2;i<n;i++){min=Maxint;for(w=1;w<=n;w++)if(!S[w]&&D2[w]<min){ //w顶点离v1顶点更近v=w;min=D2[w];}S[v]=TURE;for(w=1;w<=n;w++) //更新当前最短路径及距离if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w])){ //修改D2[w]和P2[w]D2[w]=D2[v]+G->arcs[v][w];P2[w]=v;}}printf("路径长度路径\n");for(i=1;i<=n;i++){printf("%5d",D2[i]);printf("%5d",i);v=P2[i];while(v!=0){printf("<-%d",v);v=P2[v];}printf("\n");}}（2）费洛伊德算法void Floyd(MGraph *G,int n){int i,j,k,v,w;for(i=1;i<=n;i++) //设置路径长度D和路径path初值for(j=1;j<=n;j++){if(G->arcs[i][j]!=Maxint)P[i][j]=j; //j是i的后继elseP[i][j]=0;D[i][j]=G->arcs[i][j];}for(k=1;k<=n;k++){ //做k次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径P[i][j]上for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(D[i][k]+D[k][j]<D[i][j]){D[i][j]=D[i][k]+D[k][j]; //修改长度P[i][j]=P[i][k];printf("dij=%d,pij=%d\n",D[i][j],P[i][j]);}}}}5.输入/输出数据1.测试第一个无边图2.测试第二个有向图测试均满足题目条件。

3.4邻接矩阵的显示---------------------------------------------------------------------------9
3.5递归函数的应用---------------------------------------------------------------------------10
}MGrph;//邻接矩阵表示的图
3.1.1顶点的定义typedef char VertexType;//定义图的顶点为字符型 顶点的最大个数25
3.1.2ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];二维数组用于存放邻接矩阵，每个位置代表的值为图中的权值，其余用无穷大3000表示。
}ArcCell;
typedef struct{
VertexType vexs[MAX_VERTEX_NUM];//一维数组，存储顶点
ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵 ：二维数组，存储边和弧
int vexnum,arcnum;//图的当前顶点数和弧数
2.原始数据的输入格式
2.1建图：2.1.1数字
2.2显示：2.2.1数字+逗号+数字+回车
2.2.2字母+回车
3.实现功能
3.1建立有向图
3.2显示存储的有向图
3.3显示从顶点到其他各个顶点的最短路径和是否存在路径
4.测试用例
4.1正确数据：输入顶点；边值信息
输出结果：最短路径是否存在，存在的情况最短路径是多少，其次是不存在。
第1章问题分析与任务定义
1、课程设计题目：

【数据结构算法】实验8-图的最短路径问题（附源代码）浙江大学城市学院实验报告课程名称数据结构与算法实验项目名称实验八图的最短路径问题实验成绩指导老师（签名）日期一.实验目的和要求1.掌握图的最短路径概念。

2.理解并能实现求最短路径的DijKstra算法（用邻接矩阵表示图）。

二. 实验内容1、编写用邻接矩阵表示有向带权图时图的基本操作的实现函数，基本操作包括：① 初始化邻接矩阵表示的有向带权图void InitMatrix(adjmatrixG);② 建立邻接矩阵表示的有向带权图 void CreateMatrix(adjmatrix G, int n) （即通过输入图的每条边建立图的邻接矩阵）;③ 输出邻接矩阵表示的有向带权图void PrintMatrix(adjmatrix G, int n) （即输出图的每条边）。

把邻接矩阵的结构定义以及这些基本操作函数存放在头文件Graph2.h中。

2、编写求最短路径的DijKstra算法函数 void Dijkstra( adjmatrix GA, int dist[], edgenode *path[], int i, int n) ，该算法求从顶点i到其余顶点的最短路径与最短路径长度，并分别存于数组path 和dist 中。

编写打印输出从源点到每个顶点的最短路径及长度的函数void PrintPath(int dist[], edgenode *path[], int n)。

3、编写测试程序（即主函数），首先建立并输出有向带权图，然后计算并输出从某顶点v0到其余各顶点的最短路径。

要求：把指针数组的基类型结构定义edgenode、求最短路径的DijKstra算法函数、打印输出最短路径及长度的函数PrintPath以及主函数存放在文件test9_2.cpp中。

测试数据如下：4、填写实验报告，实验报告文件取名为report8.doc。

5、上传实验报告文件report8.doc与源程序文件test9_2.cpp及Graph2.h到Ftp服务器上自己的文件夹下。

一、概述 (1)二、....................... 系统分析1三、....................... 概要设计2四、....................... 详细设计54.1建立图的存储结构 (5)4.2单源最短路径 (6)4.3任意一对顶点之间的最短路径 (7)五、运行与测试 (8)参考文献 (11)附录12交通咨询系统设计（最短路径问题）一、概述在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。

在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。

这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低等等的一系列问题。

二、系统分析设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径（里程）、最低花费或是最少时间等问题。

对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。

针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。

并未本系统设置一人性化的系统提示菜单，方便使用者的使用。

二、概要设计可以将该系统大致分为三个部分：①建立交通网络图的存储结构；②解决单源最短路径问题；③实现两个城市顶点之间的最短路径问题。

交通咨询系统迪杰斯特拉算法（单源最短路径）费洛依德算法（任意顶点对间最短路迪杰斯特拉算法流图:弗洛伊德算法流图:四、详细设计4.1建立图的存储结构定义交通图的存储结构。

邻接矩阵是表示图形中顶点之间相邻关系的矩阵。

设G=(V,E)是具有n个顶点的图，贝S G的邻接矩阵是具有如下定义的n阶方阵。

数据结构实验报告最短路径
问题
最短路径问题是指，在一个有向图中，从一个节点到另一个节点的最短路径。

它也可以用来求解其他路径问题，如求取多个源点到多个目标点之间最短路径。

本实验要实现的是最短路径问题，根据图G，利用Dijkstra算法求出源点s到其他每个顶点v的最短路径。

1. 首先，读取顶点和边的信息，并存储在相应的数据结构中；
2. 然后，以源点s为起点，遍历所有边，计算从s出发到其他顶点的最短距离，并将其标记为已被访问；
3. 接着，对于已被访问的顶点，再次遍历所有边，比较从s出发到其他顶点的最短距离，如果有更小的距离，则更新此最短距离；
4. 重复步骤2-3，直到所有顶点都被访问过；
5. 最后，打印出源点s到其他每个顶点v 的最短路径。

数据结构课程设计报告最短路径：拯救007专业 物联网工程学生姓名 班级 学号指导教师完成日期2016年1月13日目录1、课程设计目的及要求 (1)2、课题总体设计 (2)3、详细设计 (4)4、图像文件 (7)5、调试与测试 (10)6、小结 (10)7、参考文献 (16)8、源程序清单 (17)数据结构程序设计数据结构程序课程的设计1、课程设计目的及要求1）设计题目看过007系列电影的人们一定很熟悉James Bond这个世界上最著名的特工了。

在电影“Live and Let Die”中James Bond被一组毒品贩子抓住并且关到湖中心的一个小岛上，而湖中有很多凶猛的鳄鱼。

这时James Bond做出了最惊心动魄的事情来逃脱——他跳到了最近的鳄鱼的头上，在鳄鱼还没有反应过来的时候，他又跳到了另一只鳄鱼的头上……最后他终于安全地跳到了湖岸上。

假设湖是100×100的正方形，设湖的中心在（0，0），湖的东北角的坐标是（50，50）。

湖中心的圆形小岛的圆心在（0，0），直径是15。

一些凶猛的鳄鱼分布在湖中不同的位置。

现已知湖中鳄鱼的位置（坐标）和James Bond可以跳的最大距离，请你告诉James Bond一条最短的到达湖边的路径。

他逃出去的路径的长度等于他跳的次数。

2）输入要求程序从“input.txt”文件中读取输入信息，这个文件包含了多组输入数据。

每组输入数据的起始行中包含两个整数n和d，n是鳄鱼的数量而且n≤100，d是007可以跳的最大距离而且d>0。

起始行下面的每一行是鳄鱼的坐标（x，y），其中x, y都是整数，而且没有任何两只鳄鱼出现在同一个位置。

input.txt文件以一个负数结尾。

3）输出要求程序输出结果输出到output.txt文件中。

对于每组输入数据，如果007可以逃脱，则输出到output.txt文件的内容格式如下：第一行是007必须跳的最小的步数，然后下面按照跳出顺序记录跳出路径上的鳄鱼坐标（x，y），每行一个坐标。

Dgree biao[20];
int Glength;
}Mark;
void InitMark(Mark &M,int x){
int j;
M.Glength=x;
printf("请依次输入这些点:\n");
for(j=1;j<=x;j++)
{
scanf("%s",&M.biao[j].v);
M.biao[j].flag=-1;
{
int i, j, temp;
for (i = 0, j = n-1; i < j; i++, j--)
SWAP(x[i], x[j]);
}
void readin(int dist[][MAXSIZE], int *number)
{
int origin, dest, length, n;
int i, j;
}
}
void HeadAdjust(Headtype &H,int s,int m)
{ Edge rc;
int p;
rc=H.space[s];
for(p=2*s;p<=m;p*=2)
{
if(p<m&&(H.space[p].weight<H.space[p+1].weight))
++p;
if(rc.weight>H.space[p].weight)
void display_path(int [][MAXSIZE], int [][MAXSIZE], int);
void reverse(int [], int);