单源最短路径实验报告

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

2、步，直到所有候选集点都被加入到终点集中。关键代码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)&(distjtemp) u=j;temp=distj;su=tr

3、ue;for(int j=1;j=n;j+)int newdist=distu+cuj;if(newdistdistj)distj=newdist;prevj=u;手动输入实现实验所给图形：请瓶bAJ贝鼎魏：路径；0 4 2 5 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 7 5 1000 1000 1000 1000 1000 1000 0 1000 1000 9 1000 1000 1000 1000 1000 1000 1000 0 2 1000 7 1000 1000 1000 1000 1000 1000 1000 0 1000 10

4、00 4 1000 1000 1000 10001000100010000 1000 1000100061000 100010001000100010000 10003 10001000 100010001000100010001000 0100071000 100010001000100010001000 1000 081000 1000 1000 1000 1000 1000 1000 1000 1000 1000 请输入源点=1测试结果1到1的最短路径为；I 1到2的最短路径为：4 1到3的最短路径为=2 1到4的最短路径为=5 1到5的最短路径为；7 1到6的最短路径为二9 1到7的最

5、短路径为M 12 1到的最短路径为=11 1到9的最短路径为;15 1到1。的最短路径为:15随机数产生图的权值:请输入顶点数= 请推入源点：51路径；042100035110000100025 10001000 10000 100061000 1000460 10001000281000 100001到1的最短路径为：01到2的最短路径为；291到3的最短路径为；S11到4的最短路径为，351到5的最短路径为：1请输入顶点数=6 请新入晶点二2路径，0 1000 1000400291000 1000010002510001000 1000 100027 1000 1000蛭Lil的最短路径为

6、: 2至脂的最短路径丸 2到3的最短路径为; 2到4的最短路径为: 2到5的最短路径丸 蛭伯的最短路径丸361000100010004910002312150341000100001000100033040029524144通过这次实验，我回顾了回溯法求解最短路径问题，在其中加入了舍伍德 随机化取值过程，使数据分布更加均匀，让我熟悉了随机化算法，也让结果更 加公平可靠。实验心得本次实验在书本有详细的算法，很容易实现了上面的图形，但是为了改进 算法，实现取随机数组成一个图，在取随机数组成的权值时有点小麻烦，由于 刚开始时只考虑到某些顶点不联通，要把部分随机数取成较大的无效值，后又 发现没有考虑到

7、图的双向问题，分别给两个方向都取了随机值，于是结果出现 差错，于是增加了一个判断条件使图成为一个单向图，通过手动输入起点的方 式实现最短路径搜索。通过这次实验，不仅掌握了贪心算法，还掌握了随机产生一个图并计算其 最短路径的算法，让我觉得收获颇大。实验得分助教签名附录：完整代码#include#include#include#define maxint 1000int c200200 = 0;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

8、=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(newdistIo s 宅 +OOSOSH 3 (OOOIHm,-)0)二(OHSSW 出)(78出 麝抵弗/ 一夫(Bm 履 Lpr) JusLp* “救妲噩曝嘴足 p 滇宿 p*ur)JAUd)(+I二+UI二已 AUPJOtH-(AoJd us-l-lpd