贪心算法实验求解最短路径

1、算法分析与设计实验报告第 五 次实验姓名学号班级时间12.12上午地点工训楼309 实验名称贪心算法实验(求解最短路径)实验目的通过上机实验，要求掌握贪心算法的思想，利用Dijkstra算法求解最短路径并实现。实验原理设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一

2、旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。实验步骤（1）用邻接矩阵表示有向图，并进行初始化，同时选择源点；（2）选取候选集中距离最短的顶点，把其加入终点集合中；（3）以该顶点为新考虑的中间顶点，修改候选集中个顶点距离，若经过该点后，各点到达源点距离比原来距离短，则修改距离；（4）重复以上2、3步，直到所有候选集中都被加入到终点集中。关键代码template<class Type>/参数分别为顶点个数n，源结点v，源结点到其他结点的距离数组dist，父结点数组prev，各结点之间的距离数组cN+1void Dijkstra(int n,int v,

3、Type dist,int prev,Type cN+1)bool sN+1; /s数组表示各结点是否已经遍历for(int i=1;i<=n;i+)disti=cvi;/disti表示当前从源到顶点i的最短路径长度si=false;if(disti=M)previ=0;/记录从源到顶点i的最短路径的前一个顶点elseprevi=v;distv=0;sv=true;for(int i=1;i<n;i+)int temp=M;int u=v;/上一个顶点/取出v-s中具有最短路径长度的顶点ufor(int j=1;j<=n;j+)if(!sj)&&(distj&

4、lt;temp)/如果distj比最小值temp小并且没有在集合s中u=j;temp=distj;/更新最小值tempsu=true;/根据做出的贪心选择更新dist的值for(int j=1;j<=n;j+)/当加入S集合后，更新dist的值if(!sj)&&(cuj<M)Type newdist=distu+cuj;if(newdist<distj)distj=newdist;prevj=u;测试结果输入较小的有向带权图结果： 输入较大的有向带权图结果： 实验分析在实验中输入了两个有向带权图，一组是结点较少，贪心判断会少一点，另一组的结点稍微多一点，贪心判

5、断会多一些，通过上面的图和下面的结果的比较，我们可以发现结果是正确的，说明程序设计没有问题。观察两个图所用的时间的多少，我们发现这两个结点所用的时间是相对接近的，并没有很大的差距。不过这一个程序有一个问题就是每一次都需要我们手动的去输入一个图的邻接矩阵，对于结点很多的图显然是不合适，所以我们可以通过读文件来减少工作量，下次要改进。实验心得Dijkstra算法在之前的数据结构中就学过，在当时只是学过这种思想，并没有去深思这种思想其背后到底是一种怎样的思想在里面。后来经过本门课的学习，对于贪心算法有了更深刻的了解，也知道了如何利用贪心算法去解决问题。最开心的是经过一定时间的练习，我的编程能力有了一

6、定的提高，之前看见就很头疼的问题，现在也能静下心来去思考，而且实现Dijkstra算法也可以通过一定程度的思考也能写出来了，感觉还是很开心的。Dijkstra算法求单源最短路径在很多地方都有应用，经过一次又一次的练习，终于能好好的掌握这一算法了，还是希望不要那么快忘记啊。实验得分助教签名附录：完整代码（贪心法）/贪心算法 Dijkstra求单源最短路径#include<iostream>#include<string>#include<time.h>#include<iomanip>using namespace std;const int N=

7、10;const int M=1000; /定义无限大的值template<class Type>void Dijkstra(int n,int v,Type dist,int prev,Type cN+1);/输出最短路径，源点v，终点i，prev保存父结点void Traceback(int v,int i,int prev);/参数分别为顶点个数n，源结点v，源结点到其他结点的距离数组dist，父结点数组prev，各结点之间的距离数组cN+1template<class Type>void Dijkstra(int n,int v,Type dist,int pr

8、ev,Type cN+1)bool sN+1; /s数组表示各结点是否已经遍历for(int i=1;i<=n;i+)disti=cvi; /disti表示当前从源到顶点的最短路径长度si=false;if(disti=M)previ=0; /记录从源到顶点i的最短路径的前一个顶点elseprevi=v;distv=0;sv=true;for(int i=1;i<n;i+)int temp=M;int u=v; /上一个顶点/取出v-s中具有最短路径长度的顶点ufor(int j=1;j<=n;j+)if(!sj)&&(distj<temp)/如果dis

9、tj比最小值temp小并且j没有在s集合中u=j;temp=distj; /更新最小值tempsu=true;/根据做出的贪心选择更新dist的值for(int j=1;j<=n;j+) /当¡加入S集合后，更新dist的值if(!sj)&&(cuj<M)Type newdist=distu+cuj;if(newdist<distj)distj=newdist;prevj=u;/输出最短路径，v源点，i终点，prev为父结点数组void Traceback(int v,int i,int prev)if(v=i)cout<<i;retur

10、n;Traceback(v,previ,prev); /回溯输出最短路径cout<<"->"<<i;int main()int i,j;int v=1; /源点为1int distN+1,prevN+1,cN+1N+1;cout<<"有向图权的矩阵为："<<endl;for(i=1;i<=N;i+) /输入邻接矩阵for(j=1;j<=N;j+)cin>>cij;clock_t start,end,over; /计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock(); Dijkstra(N,v,dist,prev,c); /调用dijkstra算法函数for(i=2;i<=N;i+)cout<<"源点1到点"<<i<<"的最短路径长度为："<<disti<<"，其路径为：" /输出最短路径长度Tr