《单源最短路径(贪心法)实验报告(共5页).docx》由会员分享,可在线阅读,更多相关《单源最短路径(贪心法)实验报告(共5页).docx(5页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上算法分析与设计实验报告第 5 次实验姓名学号班级时间12.12下午地点四合院 实验名称贪心法求最短路径实验目的通过上机实验,掌握贪心算法的思想,利用 Dijkstra 算法求解最短路径并实现。实验原理使用贪心法求出给定图各点的最短路径,并计算算法的执行时间,分析算法的有效性。已知一个有向网络 G=(V,E)和源点 V1,如上所示,求出从源点出发到图中其余顶点的最短路径。实验步骤1 用邻接矩阵表示有向图,并进行初始化,同时选择源点;2 选取候选集中距离最短的顶点,把其加入终点集合中;3 以该顶点为新考虑的中间顶点,修改候选集中各顶点距离,若经过该点后,各点到达源点距离比
2、原来距离短,则修改距离;4 重复以上 2、3 步,直到所有候选集点都被加入到终点集中。关键代码void Dijkstra(int n,int v,int dist,int prev)bool smaxint;for(int i=1;i=n;i+)disti=cvi;si=false;if(disti=maxint) previ=0;else previ=v; /找到第一个可行源点 s标志,记录prev前一个点 distv=0;sv=true;for(int i=1;in;i+)int temp=maxint;int u=v;for(int j=1;j=n;j+)if(!sj)&(distjte
3、mp)u=j;temp=distj;su=true;for(int j=1;j=n;j+)int newdist=distu+cuj;if(newdistdistj)distj=newdist;prevj=u;测试结果手动输入实现实验所给图形:随机数产生图的权值:实验心得通过这次实验,我回顾了回溯法求解最短路径问题,在其中加入了舍伍德随机化取值过程,使数据分布更加均匀,让我熟悉了随机化算法,也让结果更加公平可靠。本次实验在书本有详细的算法,很容易实现了上面的图形,但是为了改进算法,实现取随机数组成一个图,在取随机数组成的权值时有点小麻烦,由于刚开始时只考虑到某些顶点不联通,要把部分随机数取成较
4、大的无效值,后又发现没有考虑到图的双向问题,分别给两个方向都取了随机值,于是结果出现差错,于是增加了一个判断条件使图成为一个单向图,通过手动输入起点的方式实现最短路径搜索。通过这次实验,不仅掌握了贪心算法,还掌握了随机产生一个图并计算其最短路径的算法,让我觉得收获颇大。实验得分助教签名附录:完整代码#include#include#include#define maxint 1000 int c200200=0;void Dijkstra(int n,int v,int dist,int prev)bool smaxint;for(int i=1;i=n;i+)disti=cvi;si=fal
5、se;if(disti=maxint) previ=0;else previ=v; /找到第一个可行源点 s标志,记录prev前一个点 distv=0;sv=true;for(int i=1;in;i+)int temp=maxint;int u=v;for(int j=1;j=n;j+)if(!sj)&(distjtemp)u=j;temp=distj;su=true;for(int j=1;j=n;j+)int newdist=distu+cuj;if(newdistdistj)distj=newdist;prevj=u;int main()int n,v;printf(请输入顶点数: )
6、; scanf(%d,&n);/printf(路径: ); srand(time(0);for(int i=1;in+1;i+) for(int j=1;j50) cij=1000; printf(请输入源点: ); scanf(%d,&v);int distn+1,prevn+1;printf(n路径:n);for(int i=1;in+1;i+)for(int j=1;jn+1;j+)printf(%5d ,cij);printf(n); Dijkstra(n,v,dist,prev); for(int i=1;in+1;i+) printf(n%d到%d的最短路径为:%d,v,i,disti); 专心-专注-专业