=-1）||（D[v]==-1））））
v=i;
}
returnv;
}
/*=================================================================
Dijkstra函数找到当前结点的邻接点，并更新其边权值和祖先节点。
其中记录祖先结点为方便找到路径。
*******************************************************************
pre数组记录结点的祖先结点。
pre[i]表示结点i的祖先结点。
D数组表示到源结点的距离。
D[i]表示结点i到源结点的距离。
=================================================================*/
voidDijkstra（Graph&G,int*D,ints,int*pre）
{
inti,v,w;
for（i=1;i<=G.n（）;i++）
{
//调用minVertex函数,找到未被访问的距离最小的结点
v=minVertex（G,D）;
//如果返回的为-1就表示所有结点均被访问过,结束。
if（D[v]==-1）
return;
//将找到的结点置为已访问
G.setMark（v,VISITED）;
//寻找结点的邻接点更新到起点的距离和祖先结点
for（w=G.first（v）;w<=G.n（）;w=G.next（v,w））
if（（D[w]>（D[v]+G.weight（v,w）））||（D[w]==-1））
{
D[w]=D[v]+G.weight（v,w）;//更新到起点的距离
pre[w]=v;//更新祖先结点
}
}
}
测试结果
可以看到实现了最短路径与最短路径长度的输出。
在我们给定的这个图中使用最短路径算法即Dijkstra算法的时候时间很短，可以看到算法的性质很好。
实验心得
这个Dijkstra算法真的是学烂了，加起来学了4遍多了。
所以对算法的思想还是比较了解的，但是代码编写起来还是有各种问题。
还记得上学期第一次学Dijkstra算法的时候，就要做实验写代码，那个时候三个人一个组，然后都花了很久的时间才搞定了一个结构体实现的代码。
这次的实现，我选择使用类来实现，与结构体比起来有一个优势就是，结构体实现需要定义两个结构体，另外还需要些很多函数。
使用类的话就只用写一个类，然后将函数都写在类里面。
虽然使用类和结构体实现不同，但是其大致思路和代码都差不多。
但是这个类的实现代码我却写了很久，可能是一开始的时候没有厘清思路，各种初始化没弄好，就一直中断。
但是改到最后才发现，其实是因为最主要的一个问题没处理好，就是传递的参数，因为我的图传递的时候没有使用指针，所以就有一个问题，就是在每个函数里对图进行的修改没有办法在调用它的函数中看见，所以一直出现问题，最后一个小小的&符号解决了所有的问题。
其实一开始的实现是只能输出最短路径的长度，不能输出最短路径是什么的。
但是后来增加了几个数组之后就实现了输出最短路径。
这个也要在理解算法思想的基础下才好实现。
只要增加数组来记录是哪个结点到当前结点的，即祖先结点。
这样进行反向寻找就可以找到路径输出了。
通过这次实验，我更加熟练的掌握了Dijkstra算法，相信经过这么多次Dijkstra算法的学习与代码的编写，以后一定可以熟练使用Dijkstra算法。
实验得分
助教签名
附录：
完整代码
#include
#include
#include
#include
#include
#defineUNVISITED0
#defineVISITED1
usingnamespacestd;
/*============================================================================
定义图类来存储图的信息。
============================================================================*/
classGraph
{
private:
intnumVertex;//图的顶点数
int**matrix;//图的边权值
int*mark;//记录顶点是否被访问
public:
//构造函数
Graph（intnumVert）
{
Init（numVert）;
}
//析构函数
//删除动态分配的内存
~Graph（）
{
delete[]mark;
for（inti=0;i<=numVertex;i++）
delete[]matrix[i];
delete[]matrix;
}
//初始化函数
voidInit（intn）
{
inti;
numVertex=n;
mark=newint[n+1];
//将所有结点初始化为为被访问的
for（i=0;i<=numVertex;i++）
mark[i]=UNVISITED;
//动态内存分配
matrix=（int**）newint*[numVertex+1];
for（i=0;i<=numVertex;i++）
matrix[i]=newint[numVertex+1];
//将所有边权值设为-1，表示无边相连
for（i=0;i<=numVertex;i++）
for（intj=0;j<=numVertex;j++）
matrix[i][j]=-1;
}
//求顶点数函数
intn（）
{
returnnumVertex;
}
//求第一个邻接点
//求得第一个边并返回顶点编号
intfirst（intv）
{
inti;
for（i=1;i<=numVertex;i++）
if（matrix[v][i]!
=-1）//有边相连
returni;
returni;
}
//求下一个邻接点
//求得某个结点的下一个邻接点并返回顶点编号
intnext（intv,intw）
{
inti;
//因为当前邻接点为w，求下一个的话就是从w+1开始
for（i=w+1;i<=numVertex;i++）
if（matrix[v][i]!
=-1）//有边相连
returni;
returni;
}
//设置边的权值的函数
voidsetEdge（intv1,intv2,intwt）
{
matrix[v1][v2]=wt;//将结点v1和结点v2之间的边权值设为wt
}
//查看某个边的权值
intweight（intv1,intv2）
{
returnmatrix[v1][v2];//结点v1和结点v2之间的边权值
}
//查看某个结点是否被访问过
intgetMark（intv）
{
returnmark[v];//返回结点v的mark值
}
//设置某个结点的标志,即是否被访问过
voidsetMark（intv,intval）
{
mark[v]=val;//将结点v的标志设为val
}
};
intminVertex（Graph&G,int*D）;
voidDijkstra（Graph&G,int*D,ints,int*pre）;
/*============================================================================
main函数是主函数。
构造出给定的图的邻接矩阵。
进行一些必要的初始化。
之后调用Dijkstra函数，求出最短路径长度，得到记录路径的pre数组。
根据pre数组，求出最短路径。
找出到终点的路径，存储在trave_pre数组中。
因为trave_pre数组中存储的为倒序的路径，所以反向输出即为路径。
============================================================================*/
intmain（）
{
cout<<"================================"<cout<<"==============START============="<cout<<"================================"<GraphG（10）;
intD[11];
intpre[11];
inttrave_pre[11];
inti,j;
intstart_node;
intend_node;
//各点至起点的距离初始化为-1
for（i=0;i<=G.n（）;i++）
{
D[i]=-1;
pre[i]=0;
trave_pre[i]=0;
}
//有边相连的更新其边值
G.setEdge（1,2,4）;G.setEdge（1,3,2）;G.setEdge（1,4,5）;
pre[2]=1;pre[3]=1;pre[4]=1;
G.setEdge（2,5,7）;G.setEdge（2,6,5）;
G.setEdge（3,6,9）;
G.setEdge（4,5,2）;G.setEdge（4,7,7）;
G.setEdge（5,8,4）;
G.setEdge（6,10,6）;
G.setEdge（7,9,3）;
G.setEdge（8,10,7）;
G.setEdge（9,10,8）;
//求每个结点的祖先结点
for（intk=1;k<=G.n（）;k++）
{
for（intm=1;m<=G.n（）;m++）
if（（G.weight（k,m）=-1）
pre[m]=k;
}
//输入起点
cout<<"请输入起点：
";
cin>>start_node;
//将起点置为已访问
G.setMark（start_node,VISITED）;
//输入终点
cout<<"请输入终点：
";
cin>>end_node;
//更新到起点的距离D值
for（intk=1;k<=G.n（）;k++）
D[k]=G.weight（start_node,k）;
//开始计时
clock_tstart,end,over;
start=clock（）;
end=clock（）;
over=end-start;
start=clock（）;
//调用函数
Dijkstra（G,D,start_node,pre）;
//结束计时
end=clock（）;
cout<<"================================"<cout<<"============输出结果============"<cout<<"================================"<//输出路径：
cout<<"路径为：
"<//将找出到终点的路径，存储在trave_pre数组中
for（intt=1,i=end_node;（pre[i]!
=0）;i=pre[i]）
{
trave_pre[t]=pre[i];
t++;
}
//因为trave_pre数组中存储的为倒序的路径，所以反向输出即为路径
for（intt=G.n（）;t>=1;t--）
{
if（trave_pre[t]!
=0）
cout<";
}
//输出终点
cout<//输出最短路径多长
cout<<"最短路径为：
"<//输出时间
printf（"Thetimeis%6.3f\n",（double）（end-start-over）/CLK_TCK）;
cout<cout<<"================================"<cout<<"===============END=============="<cout<<"================================"<return0;
}
/*============================================================================
minVertex返回当前到起点距离最小的未被访问的结点。
思路：
首先按顺序找到一个未被遍历的结点；
然后将此结点与后面的结点比较，找到距离最小的结点。
******************************************************************************
D数组表示到源结点的距离。
D[i]表示结点i到源结点的距离。
============================================================================*/
intminVertex（Graph&G,int*D）
{
inti;
intv=0;
for（i=1;i<=G.n（）;i++）
//找第一个未被访问的结点
if（G.getMark（i）==UNVISITED）
{
v=i;
break;
}
for（i++;i<=G.n（）;i++）
{
//找距源结点距离最小的未被访问的顶点
if（G.getMark（i）==UNVISITED&&（（（（D[i]=-1）||（D[v]==-1））））
v=i;
}
returnv;
}
/*============================================================================
Dijkstra函数找到当前结点的邻接点，并更新其边权值和祖先节点。
其中记录祖先结点为方便找到路径。
******************************************************************************
pre数组记录结点的祖先结点。
pre[i]表示结点i的祖先结点。
D数组表示到源结点的距离。
D[i]表示结点i到源结点的距离。
============================================================================*/
voidDijkstra（Graph&G,int*D,ints,int*pre）
{
inti,v,w;
for（i=1;i<=G.n（）;i++）
{
//调用minVertex函数,找到未被访问的距离最小的结点
v=minVertex（G,D）;
//如果返回的为-1就表示所有结点均被访问过,结束。
if（D[v]==-1）
return;
//将找到的结点置为已访问
G.setMark（v,VISITED）;
//寻找结点的邻接点更新到起点的距离和祖先结点
for（
升级会员 