单源最短路径(贪心法)实验报告(共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;i<n;i+)int temp=maxint;int u=v;for(int j=1;j<=n;j+)if(!

3、sj)&&(distj<temp)u=j;temp=distj;su=true;for(int j=1;j<=n;j+)int newdist=distu+cuj;if(newdist<distj)distj=newdist;prevj=u;测试结果手动输入实现实验所给图形：随机数产生图的权值：实验心得通过这次实验，我回顾了回溯法求解最短路径问题，在其中加入了舍伍德随机化取值过程，使数据分布更加均匀，让我熟悉了随机化算法，也让结果更加公平可靠。本次实验在书本有详细的算法，很容易实现了上面的图形，但是为了改进算法，实现取随机数组成一个图，在取随机数组成的权值时有

4、点小麻烦，由于刚开始时只考虑到某些顶点不联通，要把部分随机数取成较大的无效值，后又发现没有考虑到图的双向问题，分别给两个方向都取了随机值，于是结果出现差错，于是增加了一个判断条件使图成为一个单向图，通过手动输入起点的方式实现最短路径搜索。通过这次实验，不仅掌握了贪心算法，还掌握了随机产生一个图并计算其最短路径的算法，让我觉得收获颇大。实验得分助教签名附录：完整代码#include<stdio.h>#include<stdlib.h>#include<time.h>#define maxint 1000 int c200200=0;void Dijkstra(

5、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;i<n;i+)int temp=maxint;int u=v;for(int j=1;j<=n;j+)if(!sj)&&(distj<temp)u=j;temp=distj;su=true;for(int j=

6、1;j<=n;j+)int newdist=distu+cuj;if(newdist<distj)distj=newdist;prevj=u;int main()int n,v;printf("请输入顶点数： "); scanf("%d",&n);/printf("路径： "); srand(time(0);for(int i=1;i<n+1;i+) for(int j=1;j<n+1;j+) /* scanf("%d",&cij);*/ /手动输入 if(i!=j) if(cji=0)|(cji=1000) cij=rand()%100+1; else cij=1000; if(cij>50) cij=1000; printf("请输入源点： "); scanf("%d",&v);int distn+1,prevn+1;printf("n路径：n");for(int i=1;i<n+1;i+)for(int j=1;j<n+1;j+)printf("%5d ",cij);printf("n"