数据结构算法实验8图的最短路径问题附源代码Word文档格式.docx
《数据结构算法实验8图的最短路径问题附源代码Word文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构算法实验8图的最短路径问题附源代码Word文档格式.docx（14页珍藏版）》请在冰点文库上搜索。
实验结果与分析
包括运行结果截图等
【测试数据】
顶点数：
7
输入弧的信息：
尾顶点
头顶点
权值
1
8
3
5
2
4
10
6
15
9
正确的邻接矩阵应为：
∞
下面以测试数据为基准，给出DijKstra算法生成最短路径的状态变化图：
（※注：
顶点旁边的<
x>
代表当前状态下从源点到该顶点的最短路径长度）
【状态①】【状态②】
【状态③】【状态④】
【状态⑤】【状态⑥】
【状态⑦（最短路径）】
五.心得体会
记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。
【附录----源程序】
[]
#include<
>
#include"
"
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<
**************以下为DijKstra算法部分**************"
endl;
Dijkstra（G,dist,path,0,n）;
PrintPath（dist,path,n）;
}
//求最短路径的DijKstra算法函数
voidDijkstra（adjmatrixGA,intdist[],edgenode*path[],inti,intn）{
intj,k;
intv=1,minIndex;
voidPATH（edgenode*path[],inti,intj）;
bool*isStepped;
//初始化部分
//isStepped：
申请n个空间，除i以外均为false
//dist：
邻接矩阵中i顶点到各顶点的距离
//path：
邻接矩阵中i顶点到各顶点若有路径，则保存；
无路径置为NULL
isStepped=newbool[n];
for（j=0;
j<
n;
j++）{
dist[j]=GA[i][j];
if（dist[j]!
=MaxValue&
&
j!
=i）{
path[j]=newedgenode;
path[j]->
adjvex=i;
next=newedgenode;
next->
adjvex=j;
next=NULL;
}
elsepath[j]=NULL;
isStepped[j]=false;
}
isStepped[i]=true;
while（v<
=n）{
//尝试查找当前最小路径结点，用minIndex保存顶点
minIndex=i;
for（k=0;
k<
k++）{
if（dist[k]<
dist[minIndex]&
（!
isStepped[k]））
minIndex=k;
//有查找到最小路径顶点，则将其并入集合
if（minIndex!
=i）
isStepped[minIndex]=true;
//未查找到，则说明路径都为∞，退出
else
break;
//通过while中确定的最小路径顶点（minIndex）到达当前顶点
//若路径长度小于dist中保存的路径长度，则修改
if（GA[minIndex][k]+dist[minIndex]<
dist[k]）{
dist[k]=GA[minIndex][k]+dist[minIndex];
PATH（path,k,minIndex）;
}
v++;
//将path[i]的路径改为path[j]的路径+i
voidPATH（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]->
while（t!
q=p;
p=newedgenode;
p->
adjvex=t->
q->
next=p;
t=t->
//将j结点加入path[i]的路径中
q=p;
q->
//打印输出从源点到每个顶点的最短路径及长度的函数
voidPrintPath（intdist[],edgenode*path[],intn）{
inti;
edgenode*p;
for（i=1;
i<
i++）{
cout<
[v0->
v"
i<
]"
最短路径：
;
p=path[i];
if（p==NULL）{
cout<
无路径！
continue;
while（p!
v"
p->
adjvex<
"
p=p->
最短长度：
dist[i]<
//图的最大顶点数
constintMaxEdgeNum=100;
//边数的最大值
constintMaxValue=32767;
//权值的无穷大表示
typedefintadjmatrix[MaxVertexNum][MaxVertexNum];
//邻接矩阵
//①初始化邻接矩阵表示的有向带权图
voidInitMatrix（adjmatrix&
G）
{
inti,j;
for（i=0;
i<
MaxVertexNum;
i++）//邻接矩阵初始化
for（j=0;
j<
j++）
G[i][j]=MaxValue;
//②建立邻接矩阵表示的有向带权图（即通过输入图的每条边建立图的邻接矩阵）
voidCreateMatrix（adjmatrix&
G,intn）
intv,w,q;
按照：
尾顶点名->
头顶点名，权值输入数据，以0->
0,0结尾:
如A->
B,23\n"
while（true）{//构造邻接矩阵
%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）
----------------------------------------------------"
YourGraphis:
n;
i++）{
j++）{
if（G[i][j]!
=MaxValue）printf（"
%2d|"
G[i][j]）;
elseprintf（"
∞|"
\n"
升级会员 