数据结构算法实验8图的最短路径问题附源代码.docx
《数据结构算法实验8图的最短路径问题附源代码.docx》由会员分享，可在线阅读，更多相关《数据结构算法实验8图的最短路径问题附源代码.docx（16页珍藏版）》请在冰点文库上搜索。
数据结构算法实验8图的最短路径问题附源代码
浙江大学城市学院实验报告
课程名称 数据结构与算法
实验项目名称 实验八图的最短路径问题
实验成绩 指导老师（签名） 日期
一.实验目的和要求
1.掌握图的最短路径概念。
2.理解并能实现求最短路径的DiｊKstｒa算法（用邻接矩阵表示图）。
二.实验内容
1、编写用邻接矩阵表示有向带权图时图的基本操作的实现函数,基本操作包括：
①初始化邻接矩阵表示的有向带权图 vｏｉdIｎitＭatrix（aｄjmａtriｘG）;
②建立邻接矩阵表示的有向带权图voidCrｅaｔeＭatrix（adjmaｔrixG,intｎ）（即通过输入图的每条边建立图的邻接矩阵）;
③输出邻接矩阵表示的有向带权图voiｄＰrintMａtriｘ（adｊｍatriｘG，ｉntn）（即输出图的每条边）。
把邻接矩阵的结构定义以及这些基本操作函数存放在头文件Ｇraph2.h中。
2、编写求最短路径的ＤijKstra算法函数voidDｉｊkstra（adｊmatrｉｘ ＧA, int diｓt[], ｅdgenode ＊path[],iｎt ｉ,int n）,该算法求从顶点i到其余顶点的最短路径与最短路径长度,并分别存于数组path和diｓt 中。
编写打印输出从源点到每个顶点的最短路径及长度的函数voｉd ＰrｉntPath（ｉntdist[], edｇeｎｏdｅ*ｐａtｈ[]，ｉnt n）。
3、编写测试程序（即主函数），首先建立并输出有向带权图，然后计算并输出从某顶点v０到其余各顶点的最短路径。
要求：
把指针数组的基类型结构定义edgｅnodｅ、求最短路径的DijKstｒａ算法函数、打印输出最短路径及长度的函数ＰrｉｎtＰath以及主函数存放在文件teｓt9_２.cpｐ中。
测试数据如下:
４、填写实验报告，实验报告文件取名为ｒｅｐort8.doｃ。
5、上传实验报告文件report8.doc与源程序文件test9_2.cpp及Grapｈ2.h到Ftp服务器上自己的文件夹下。
三.函数的功能说明及算法思路
包括每个函数的功能说明,及一些重要函数的算法实现思路
【结构说明】
constiｎt MaｘVertexNum=10;//图的最大顶点数
consｔｉnt MaxＥdgｅNum＝1０0;／/边数的最大值
coｎｓtintMaxValｕe=3２767;//权值的无穷大表示
ｔypedef ｉｎtadjmatrix[ＭａxVｅrtｅｘＮum][MaxVｅrｔexNｕm]; /／邻接矩阵
typedeｆstｒuｃt Nodｅ{
intadjveｘ；
ｓtｒｕcｔNode *nｅxt;
}edgeｎode;//路径结点
【函数说明】
① voｉd InitMａtｒix（adjｍａtrｉx&Ｇ）
功能：
初始化邻接矩阵表示的有向带权图
思路：
将邻接矩阵中的所有权值设置为无穷大（ＭａxVaｌue）
②vｏiｄCreateMａｔrix（adjmatｒｉx &G, iｎｔｎ）
功能：
建立邻接矩阵表示的有向带权图（即通过输入图的每条边建立图的邻接矩阵）
思路:
按照输入的顶点信息和权值信息，更新邻接矩阵内对应的值
③vｏidPｒiｎtMatrｉx（ａdjmａｔrｉx G,intｎ）
功能：
输出邻接矩阵表示的有向带权图（即输出图的每条边）
思路：
按照一定的格式输出邻接矩阵
④ｖoidＤijkstra（adjmaｔriｘGA, inｔdisｔ[]， edgｅnode＊patｈ[］，int i, int n）
功能：
求最短路径的DijKstra算法函数
思路:
按照从源点到其余每一顶点的最短路径长度递增的次序依次求出从源点到每个顶点的最短路径及长度。
设立一个集合S，用以保存已求得最短路径的终点,其初值为只有一个元素，即源点;一个数组diｓt[n］,其每个分量dｉsｔ[ｊ]保存从源点经过S集合中顶点最后到达顶点 j的路径中最短路径的长度,其初值为从源点到每个终点的弧的权值（没弧则置为∞）；一个指针数组paｔh[ｎ］,path[j]指向一个单链表，保存相应于ｄist[j]的从源点到顶点j 的最短路径（即顶点序列），初值为空。
⑤ ｖoidPＡTH（edgenｏde*path［],inti, ｉntｊ）
功能：
将ｐath［i]的路径改为ｐａth[j］的路径+i
思路:
分为三个步骤:
一,删除path[i]中原来保存的链表;二，将ｐaｔh[j]的路径复制给path［i］；三，将j结点加入paｔh[i]的路径中
⑥vｏid PrｉntＰath（int dｉst[]， edgeｎoｄｅ*ｐatｈ[］, inｔ n）{
功能:
打印输出从源点到每个顶点的最短路径及长度的函数
思路:
按照一定的格式遍历输出从源点到每个顶点的最短路径及长度
四.实验结果与分析
包括运行结果截图等
ﻩ【测试数据】
顶点数:
7
输入弧的信息:
尾顶点
头顶点
权值
０
1
8
0
3
5
1
２
２
1
4
10
2
4
6
2
５
5
3
1
3
３
5
7
３
6
１5
6
5
9
正确的邻接矩阵应为:
∞
8
∞
４
∞
∞
∞
∞
∞
2
∞
10
∞
∞
∞
∞
∞
∞
6
５
∞
∞
3
∞
∞
∞
7
15
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
９
∞
∞
∞
∞
∞
∞
∞
∞
∞
下面以测试数据为基准,给出ＤiｊＫstra算法生成最短路径的状态变化图：
（※注:
顶点旁边的
【状态①】 【状态②】
【状态③】 【状态④】
【状态⑤】 【状态⑥】
【状态⑦（最短路径）】
五．心得体会
记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。
【附录----源程序】
[Ｔest9＿2.cpp］
#ｉnclｕdｅ
#iｎclude＜sｔdlib．h>
#ｉnclude<ｉostream．h＞
#includｅ＜stｒing.h>
＃inclｕｄe"Grａph2.h＂
tyｐedefsｔructNode{
ｉnt ａｄjveｘ;
stｒuｃt Ｎodｅ ＊next;
}edgenode;
ｖoid maiｎ（）｛
ﻩintn;
ａdｊmatrix G;
ｅdｇeｎode＊patｈ[MaxVｅｒtexNｕm];
ﻩinｔｄｉｓt[MaxVertexNum］；
ﻩｖｏiｄDijkstra（ adｊmatｒixGＡ,iｎtdist[］, edgenoｄe *ｐath[],inti, intn）;
vｏidPrｉntPaｔh（ｉnt ｄisｔ［],edｇｅnodｅ＊ｐath［],iｎtn）;
ﻩIｎitＭatrｉｘ（G）;
ﻩｐrｉntf（"输入要构造的图顶点数＼n"）;
scanｆ（"％ｄ",&n）;
CreａteMatｒix（Ｇ,n）;
PrintMａtriｘ（G，n）； ／/打印图的邻接矩阵
ﻩｃout<＜enｄl<＜enｄl<<＂*****＊**＊***＊*以下为ＤiｊＫstｒa算法部分*****＊*****＊**"<ﻩDijkstrａ（G, dｉsｔ,paｔh,0,n）;
PｒintPａtｈ（dist，path,n）;
}
/／求最短路径的DijKstra算法函数
vｏiｄ Ｄｉjｋｓtｒa（adjmａtrixＧA, ｉｎtdisｔ［]， edgｅnoｄｅ＊path[］, ｉnti,iｎtn）{
ﻩintj，k;
ﻩiｎt ｖ= 1，minInｄｅx;
ﻩｖoidＰＡTＨ（ｅdｇｅnoｄe *pａｔｈ[]， int ｉ, int j）;
bool*iｓStepped；
ﻩ//初始化部分
ﻩ//isStｅppｅd：
申请n个空间，除ｉ以外均为fａlse
／/ｄｉst:
邻接矩阵中i顶点到各顶点的距离
ﻩ//patｈ：
邻接矩阵中i顶点到各顶点若有路径，则保存;无路径置为ＮＵLL
ﻩiｓStepped=newbool［ｎ]；
for（j =０; ｊ ﻩdist［j]=GA［i][j］;
if（ｄist[ｊ] !
＝MａxVaｌue&& j!
=ｉ）｛
ｐatｈ［ｊ]＝neｗｅdgenode；
ﻩｐａth[ｊ]－>ａdｊvex =ｉ;
ﻩpath[j］-＞ｎext＝ newedｇenode;
ﻩﻩｐath[j]-＞next->adｊvex =j；
ﻩﻩpath[ｊ]－>nｅxt->next=NULL;
ﻩ｝
elｓｅpaｔh［j]=ＮＵLL；
ﻩisSｔeｐpｅd［j]＝ｆalse；
ﻩ｝
ｉsＳteppｅd[i]=truｅ;
wｈilｅ（v<=n）｛
ﻩ//尝试查找当前最小路径结点，用mｉnＩndeｘ保存顶点
ﻩminIndex=i;
for （k=０; ｋ<ｎ;k++）{
ﻩif（ｄｉsｔ[k] iｓStepped［ｋ］））
ﻩﻩﻩmｉnIｎdex＝ k;
ﻩ}
ﻩﻩ/／有查找到最小路径顶点，则将其并入集合
if（minIndex!
=i）
ﻩisＳteppeｄ[minIｎdeｘ]=ｔrue；
ﻩﻩ/／未查找到，则说明路径都为∞,退出
ﻩﻩｅlse
ﻩｂｒeak;
//通过whｉle中确定的最小路径顶点（ｍｉnＩｎdex）到达当前顶点
ﻩ／／若路径长度小于ｄist中保存的路径长度，则修改
ﻩﻩfor（ｋ = 0;k< n; k++）｛
ﻩﻩif（GA[miｎIndeｘ］［k］+dist［mｉnInｄｅｘ]< ｄiｓt［ｋ］）{
ﻩﻩdisｔ[k]= GA[ｍinIｎｄｅｘ][ｋ]+ｄist[miｎInｄex];
ﻩﻩﻩﻩPＡTH（path，ｋ,ｍiｎIｎｄex）；
}
ﻩ}
ﻩﻩv++;
｝
}
／/将ｐatｈ[i]的路径改为ｐaｔｈ[ｊ]的路径+i
ｖｏidＰＡTＨ（edgeｎode*pａth［]，int i, iｎtｊ）{
ﻩedgｅnode*ｐ，*q,*t;
ﻩ//删除patｈ[i］中原来保存的链表
ﻩｗhile（path[ｉ］!
＝ NＵLL）｛
ﻩﻩｐ=ｐatｈ[ｉ]-＞neｘt;
ﻩﻩdｅｌｅte pａth[i];
ﻩｐaｔｈ[i］= p；
｝
ﻩ//将ｐａtｈ[ｊ]的路径复制给paｔh[i］
p =newｅｄgenode;
ｐ->aｄjｖｅx ＝ ｐath[j]->aｄjvex;
ﻩpath[i]=ｐ;
t=ｐａth［j]->neｘｔ;
ｗhilｅ（ｔ!
＝NＵLＬ）｛
ﻩﻩq= p；
ﻩｐ = new edgenodｅ;
ﻩp->ａdjvex=ｔ->ａdjvex；
ｑ->next=p;
ﻩt= ｔ－>ｎeｘt；
ﻩ}
//将j结点加入ｐaｔh［i]的路径中
q＝p；
ｐ=ｎew edｇenｏde;
ﻩp－>ａdｊvex=ｉ;
ﻩp－>ｎext＝NULL;
q->neｘt=p;
}
/／打印输出从源点到每个顶点的最短路径及长度的函数
void PrinｔPath（int ｄist[],edgenode *paｔh[］,ｉｎt n）{
inｔｉ；
edgenode＊ｐ;
ﻩｆoｒ （i =1； i ﻩcout<＜＂［v0->v＂＜cout<<＂最短路径:
＂；
ﻩﻩp=ｐａth[i];
ﻩiｆ （p＝=ＮUＬL）{
ﻩﻩｃout<＜＂无路径!
＂<ﻩcoｎtinue;
ﻩ｝
while（p！
=NULL）｛
ﻩﻩｃoｕt<<"v"＜ａdｊveｘ<<""；
p＝ ｐ－>neｘt;
｝
ﻩｃｏut＜"<＜ｄisｔ[i］<＜eｎｄｌ<＜enｄl;ﻩﻩ
ﻩ}
｝
[Grapｈ２.h]
ｃｏnsｔ ｉnt MaｘＶeｒtｅxNｕm=10;／/图的最大顶点数
ｃonsｔintMaxＥdgｅＮum=１00; //边数的最大值
constinｔMａxVａlue＝32７６7；／／权值的无穷大表示
typeｄeｆint aｄjmatrix［ＭaxＶeｒtexNｕm][ＭaxVｅｒtｅxNｕm];/／邻接矩阵
//①初始化邻接矩阵表示的有向带权图
void InitMatriｘ（aｄjmaｔrix&Ｇ）
{
ﻩinｔ i,j;
for（ｉ＝０;i<ＭaｘVｅrｔexNuｍ；i+＋） /／邻接矩阵初始化
ｆoｒ（ｊ＝０;ｊ＜ＭaxＶertexNum;ｊ++）
G［i][ｊ］=ＭaｘValｕe;
}
//②建立邻接矩阵表示的有向带权图（即通过输入图的每条边建立图的邻接矩阵）
voidCreａｔeＭatrｉx（ａdjmａtrix ＆Ｇ,intn）
{
intv， w， q;
ﻩprｉntf（"按照：
尾顶点名－>头顶点名，权值输入数据，以0-＞0，0结尾:
如Ａ->B,23 \n＂）；
while（ｔrｕe）{ /／构造邻接矩阵
scanf（＂%d->％d,％d",&v，&ｗ,&q）;／/输入弧的两个定点及该弧的权重
ﻩﻩgeｔchａr（）;
ﻩﻩif（v== ０＆＆w=＝0）brｅak;
ｉｆ（v ＜0｜|v＞＝ ｎ ||w <０｜｜w＞= n）｛ceｒr<<"veｒteｘERRＯＲ!
";ｅｘiｔ
（1）;}
G[ｖ][w]=q；
}
}
//③输出邻接矩阵表示的有向带权图（即输出图的每条边）
vｏidPｒｉｎtMatrix（adjｍatｒixG，iｎtｎ）
｛
int ｉ，ｊ;
ﻩcout＜ﻩcoｕt<<"Yoｕｒ Grａphis：
＂＜<ｅｎdl<<ｅｎdl;
ｆor（i=0;i for（ｊ=0;ｊ＜ｎ;ｊ++）{
ﻩｉf（G[i][ｊ］！
=ＭaxＶalｕe）ｐrｉntf（＂％2d |＂,G[i］[j]）；
ﻩﻩelsｅpriｎtf（＂∞|"）；
｝
ﻩpriｎtｆ（"＼n"）;
ﻩ}
｝
升级会员 