单源最短路径(贪心法)实验报告

《单源最短路径(贪心法)实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法分析与设计实验报告第5次实验姓名学号班级时间12.12下午地点四合院实验名称贪心法求最戒路径实验目的通过上机实验，掌握贪心算法的思想，利用Dijkstra算法求解最用路径并实现。实验原理使用贪心法求出给定图各点的最短路径，并计算算法的执行时间，分析算法的有效性。已知一个有向网络G二(V,E)和源点VI,如上所示，求出从源点111发到图中其余顶点的最短路径。实验步骤1用邻接矩阵表示有向图，并进行初始化，同时选择源点；2选取候选集中距离最短的顶点，把其加入终点集合中；3以该顶点为新考虑的中间顶点，修改候选集中各顶点距离，若经过该点后，各点到达源点距离比原来距离短，则修改距离；4重复以上

2、2、3步，直到所有候选集点都被加入到终点集中。关键代码voidDijkstra(intn,intv,intdist[J,intprev[J){bools[maxint];for(inti=l;i<=n;i++){dist[i]二c[v][i];s[i]二false;if(dist[i]~maxint)prev[i]=0;elseprev[i]=v;}〃找到第一个可行源点s[]标志，记录prev[]前一个点dist[v]=0;s[v]=true;for(inti=l;i〈n;i++){inttemp=maxint;intu二v;for(intj=l;j<=n;j++){if((!s[j]

3、)&&(dist[j]〈temp)){U=j;temp二dist[j];}}s[u]=true;for(intj=l;j<=n;j++){intnewdist二dist[u]+c[u][j];if(nowdist

4、100061000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010000100031000100010001000010007100008100010001000测试结果请输入源点:11到1的最短路径为：1到2的最短路径为:1到3的最短路径为：1到4的最短路径为:1到5的最短路径为:1到6的最短路径为:1到7的最短路径为:1到8的最短路径

5、为:1到9的最短路径为:0425791211151到10的最短路径为:15随机数产卞图的权值:请输人顶点数:5请输入潦点:1路径=0421000351100001000251000100010000100061000100046010001000281000100001到1的最短路径为：01到2的最短路径为：291到3的最短路径为：811到4的最短路径为：351到5的最短路径为：1请输入顶点数:6请输入漏点:2tea：0100010003610001000400291000491000100010000231215100025100003410001000100010001000010

6、00271000100010003302到1的最短路径为：402到2的最廻路径为：02到3的最短路径为：292到4的最短路径为：522到5的最短路径为:412到6的最短路径为：44通过这次实验，我回顾了回溯法求解最短路径问题，在其中加入了舍伍德随机化取值过程，使数据分布更加均匀，让我熟悉了随机化算法，也让结果更加公平可靠。实验心得本次实验在书本有详细的算法，很容易实现了上血的图形，但是为了改进算法，实现取随机数组成一个图，在取随机数组成的权值时冇点小麻烦，由于刚开始时只考虑到某些顶点不联通，要把部分随机数取成较人的无效值，示又发现没有考虑到图的双向问题，分别给两个方向都取了随机值，于是

7、结來出现差错，于是增加了一个判断条件使图成为一个单向图，通过手动输入起点的方式实现最短路径搜索。通过这次实验，不仅掌握了贪心算法，还掌握了随机产生一个图并计算具最愆路径的算法，让我觉得收获颇大。实验得分助教签名附录：完整代码#include#include#include^definemaxint1000intc[200][200]={0};voidDijkstra(intn,intv,in