数据结构算法实验8图的最短路径问题附源代码.docx
- 文档编号:2537818
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:13
- 大小:78.74KB
数据结构算法实验8图的最短路径问题附源代码.docx
《数据结构算法实验8图的最短路径问题附源代码.docx》由会员分享,可在线阅读,更多相关《数据结构算法实验8图的最短路径问题附源代码.docx(13页珍藏版)》请在冰点文库上搜索。
数据结构算法实验8图的最短路径问题附源代码
浙江大学城市学院实验报告
课程名称数据结构与算法实验项目名称实验八图的最短路径问题实验成绩指导老师(签名)日期
1.实验目的和要求
1.掌握图的最短路径概念。
2.
DijKstra算法(用邻接矩阵表示图)
理解并能实现求最短路径的
2.实验内容
1、编写用邻接矩阵表示有向带权图时图的基本操作的实现函数,基本操作包括:
1初始化邻接矩阵表示的有向带权图voidInitMatrix(adjmatrixG);
2建立邻接矩阵表示的有向带权图voidCreateMatrix(adjmatrixG,intn)
(即通过输入图的每条边建立图的邻接矩阵);
3输出邻接矩阵表示的有向带权图voidPrintMatrix(adjmatrixG,intn)
(即输出图的每条边)。
把邻接矩阵的结构定义以及这些基本操作函数存放在头文件Graph2.h中。
2、编写求最短路径的DijKstra算法函数voidDijkstra(adjmatrixGA,int
dist[],edgenode*path[],inti,intn),该算法求从顶点i到其余顶点的最
短路径与最短路径长度,并分别存于数组path和dist中。
编写打印输出从源
点到每个顶点的最短路径及长度的函数voidPrintPath(intdist[],edgenode
*path[],intn)。
3、编写测试程序(即主函数),首先建立并输出有向带权图,然后计算并输出从某顶点vO到其余各顶点的最短路径。
要求:
把指针数组的基类型结构定义edgenode、求最短路径的DijKstra算法
函数、打印输出最短路径及长度的函数PrintPath以及主函数存放在文件
test9_2.cpp中。
测试数据如下:
4、填写实验报告,实验报告文件取名为report8.doc。
5、上传实验报告文件report8.doc与源程序文件test9_2.cpp及Graph2.h到Ftp服务器上自己的文件夹下。
3.函数的功能说明及算法思路
包括每个函数的功能说明,及一些重要函数的算法实现思路
【结构说明】
constintMaxVertexNum=10;//图的最大顶点数
constintMaxEdgeNum=100;//边数的最大值
constintMaxValue=32767;〃权值的无穷大表示
typedefintadjmatrix[MaxVertexNum][MaxVertexNum];//邻接矩阵typedefstructNode{
intadjvex;
structNode*next;
}edgenode;〃路径结点
【函数说明】
1voidInitMatrix(adjmatrix&G)
功能:
初始化邻接矩阵表示的有向带权图
思路:
将邻接矩阵中的所有权值设置为无穷大(MaxValue)
2voidCreateMatrix(adjmatrix&G,intn)
功能:
建立邻接矩阵表示的有向带权图(即通过输入图的每条边建立图的邻接矩阵)
思路:
按照输入的顶点信息和权值信息,更新邻接矩阵内对应的值
3voidPrintMatrix(adjmatrixG,intn)
功能:
输出邻接矩阵表示的有向带权图(即输出图的每条边)
思路:
按照一定的格式输出邻接矩阵
4voidDijkstra(adjmatrixGA,intdist[],edgenode*path[],inti,intn)
功能:
求最短路径的DijKstra算法函数
思路:
按照从源点到其余每一顶点的最短路径长度递增的次序依次求出从源点到每个顶点的最短路径及长度。
设立一个集合S,用以保存已求得最短路径的终点,其初值为只有一个元素,即源点;一个数组dist[n],其每个分量dist[j]保存从
源点经过S集合中顶点最后到达顶点j的路径中最短路径的长度,其初值为从源点到每个终点的弧的权值(没弧则置为X);—个指针数组path[n],path[j]
指向一个单链表,保存相应于dist[j]的从源点到顶点j的最短路径(即顶点序列),初值为空。
5voidPATH(edgenode*path[],inti,intj)
功能:
将path[i]的路径改为path[j]的路径+i
思路:
分为三个步骤:
一,删除path[i]中原来保存的链表;二,将path[j]的路径
复制给path[i];三,将j结点加入path[i]的路径中
6voidPrintPath(intdist[],edgenode*path[],intn){
功能:
打印输出从源点到每个顶点的最短路径及长度的函数
思路:
按照一定的格式遍历输出从源点到每个顶点的最短路径及长度
4.实验结果与分析包括运行结果截图等
【测试数据】
顶点数:
7
输入弧的信息:
尾顶点
头顶点
权值
0
1
8
0
3
5
1
2
2
1
4
10
2
4
6
2
5
5
3
1
3
3
5
7
3
6
15
6
5
9
正确的邻接矩阵应为:
OO
8
OO
4
OO
OO
OO
OO
OO
2
OO
10
OO
OO
OO
OO
OO
OO
6
5
OO
OO
3
OO
OO
OO
7
15
OO
OO
OO
OO
OO
OO
OO
OO
OO
OO
OO
9
OO
OO
OO
OO
OO
OO
OO
OO
OO
F面以测试数据为基准,给出DijKstra算法生成最短路径的状态变化图:
(※注:
顶点旁边的vxM弋表当前状态下从源点到该顶点的最短路径长度)
【状态①】
【状态②】
>
5
4
-<17>
<11>
【状态④】
【状态③】
0
4
3
3
15
5
3
1
2
6
7初
<19>
<11>
<4>
<7>
【状态⑤】
【状态⑦(最短路径)】
五•心得体会
记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。
【附录----源程序】
[Test9_2.cpp]
#include
#include
#include"Graph2.h"
typedefstructNode{intadjvex;structNode*next;
}edgenode;
voidmain(){
intn;
adjmatrixG;
edgenode*path[MaxVertexNum];
intdist[MaxVertexNum];
voidDijkstra(adjmatrixGA,intdist[],edgenode*path[],inti,intn);voidPrintPath(intdist[],edgenode*path[],intn);
InitMatrix(G);
printf("输入要构造的图顶点数\n");
scanf("%d",&n);
CreateMatrix(G,n);
PrintMatrix(G,n);//打印图的邻接矩阵
cout«endl«endlvv"**************以下为DijKstra算法部分
**************"< Dijkstra(G,dist,path,0,n); PrintPath(dist,path,n); } //求最短路径的DijKstra算法函数 voidDijkstra(adjmatrixGA,intdist[],edgenode*path[],inti,intn){ intj,k; intv=1,minlndex; voidPATH(edgenode*path[],inti,intj); bool*isStepped; //初始化部分 //isStepped: 申请n个空间,除i以外均为false //dist: 邻接矩阵中i顶点到各顶点的距离 NULL //path: 邻接矩阵中i顶点到各顶点若有路径,贝M呆存;无路径置为isStepped=newbool[n]; for(j=0;j dist[j]=GA[i][j]; if(dist[j]! =MaxValue&&j! =i){path[j]=newedgenode;path[j]->adjvex=i; path[j]->next=newedgenode; path[j]->next->adjvex=j;path[j]->next->next=NULL; elsepath[j]=NULL;isStepped[j]=false; } isStepped[i]=true; while(v<=n){ //尝试查找当前最小路径结点,用minlndex保存顶点 minlndex=i; for(k=0;k if(dist[k] isStepped[k]))minlndex=k; } //有查找到最小路径顶点,则将其并入集合 if(minlndex! =i) isStepped[minlndex]=true; //未查找到,则说明路径都为%,退出 else break; //通过while中确定的最小路径顶点(minlndex)到达当前顶点//若路径长度小于dist中保存的路径长度,则修改 for(k=0;k if(GA[minlndex][k]+dist[minlndex] } }v++; } } //将path[i]的路径改为path[j]的路径+ivoidPATH(edgenode*path[],inti,intj){edgenode*p,*q,*t; //删除path[i]中原来保存的链表 while(path[i]! =NULL){ p=path[i]->next; deletepath[i];path[i]=p; } //将path[j]的路径复制给path[i] p=newedgenode;p->adjvex=path[j]->adjvex;path[i]=p; t=path[j]->next; while(t! =NULL){ q=p; p=newedgenode;p->adjvex=t->adjvex;q->next=p; t=t->next; } //将j结点加入path[i]的路径中q=p; p=newedgenode; p->adjvex=i; p->next=NULL; q->next=p; }//打印输出从源点到每个顶点的最短路径及长度的函数voidPrintPath(intdist[],edgenode*path[],intn){ inti; edgenode*p; for(i=1;i cout<<"[v0->v"< cout«"最短路径: "; p=path[i]; if(p==NULL){ cout«"无路径! "< } while(p! =NULL){ cout<<"v"< p=p->next; } coutvvendlvv"最短长度: "< } }[Graph2.h] constintMaxVertexNum=10;//图的最大顶点数constintMaxEdgeNum=100;//边数的最大值constintMaxValue=32767;//权值的无穷大表示 typedefintadjmatrix[MaxVertexNum][MaxVertexNum];//邻接矩阵 //①初始化邻接矩阵表示的有向带权图 voidInitMatrix(adjmatrix&G) { inti,j; for(i=0;ivMaxVertexNum;i++)//邻接矩阵初始化 for(j=0;jvMaxVertexNum;j++)G[i][j]=MaxValue; } //②建立邻接矩阵表示的有向带权图(即通过输入图的每条边建立图的邻接矩阵) voidCreateMatrix(adjmatrix&G,intn) { intv,w,q; printf("按照: 尾顶点名->头顶点名,权值输入数据,以0->0,0结尾: 如 A->B,23\n"); while(true){//构造邻接矩阵 scanf("%d->%d,%d",&v,&w,&q);//输入弧的两个定点及该弧的权重getchar(); if(v==0&&w==0)break; if(v<0||v>=n||w<0||w>=n){cerr<<"vertexERROR! ";exit (1);}G[v][w]=q; } } //③输出邻接矩阵表示的有向带权图(即输出图的每条边) voidPrintMatrix(adjmatrixG,intn) { inti,j; cout«endlvv""< cout<<"YourGraphis: "< for(i=0;i for(j=0;j if(G[i][j]! =MaxValue)printf("%2d|",G[i][j]); elseprintf("|"); } printf("\n"); }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 实验 路径 问题 源代码