贪心算法实验(求解最短路径).doc

《贪心算法实验(求解最短路径).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、之间的距离数组c[][N+1]voidDijkstra(intn,intv,Typedist[],intprev[],Typec[][N+1]){bools[N+1];//s数组表示各结点是否已经遍历for(inti=1;i<=n;i++){dist[i]=c[v][i];//dist[i]表示当前从源到顶点i的最短路径长度s[i]=false;if(dist[i]==M)prev[i]=0;//记录从源到顶点i的最短路径的前一个顶点elseprev[i]=v;}dist[v]=0;s[v]=true;for(inti=1;i

4、mp=M;intu=v;//上一个顶点//取出v-s中具有最短路径长度的顶点ufor(intj=1;j<=n;j++){if((!s[j])&&(dist[j]

5、t

6、工作量，下次要改进。实验心得Dijkstra算法在之前的数据结构中就学过，在当时只是学过这种思想，并没有去深思这种思想其背后到底是一种怎样的思想在里面。后来经过本门课的学习，对于贪心算法有了更深刻的了解，也知道了如何利用贪心算法去解决问题。最开心的是经过一定时间的练习，我的编程能力有了一定的提高，之前看见就很头疼的问题，现在也能静下心来去思考，而且实现Dijkstra算法也可以通过一定程度的思考也能写出来了，感觉还是很开心的。Dijkstra算法求单源最短路径在很多地方都有应用，经过一次又一次的练习，终于能好好的掌握这一算法了，还是希望不要那么快忘记啊

7、。实验得分助教签名附录：完整代码（贪心法）//贪心算法Dijkstra求单源最短路径#include#include#include#includeusingnamespacestd;constintN=10;constintM=1000;//定义无限大的值templatevoidDijkstra(intn,intv,Typedist[],intprev[],Typec[][N+1]);//输出最短路径，源点v，终点i，prev[]保存父结点voidTraceb

8、ack(intv,inti,intprev[]);//参数分别为顶点个数n，源结点v，源结点到