计算机算法实验5

算法分析与设计实验报告第5次实验姓名曾宁学号201308030323班级通信1303时间12.12上午地点四合院实验名称贪心法求最短路径实验目的掌握贪心算法的思想，利用Dijkstra算法求解最短路径并实现。实验原理Dijkstra算法是解单源最短路径问题的贪心算法。其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。Dijkstra算法可描述如下，其中输入带权有向图是G=(V,E)，V={1,2,…，n}，顶点v是源。c是一个二维数组，c[i][j]表示边(i,j)的权。当(i,j)不属于E时，c[i][j]是一个大数。dist[i]表示当前从源到顶点i的最短特殊路径长度。在Dijkstra算法中做贪心选择时，实际上是考虑当S添加u之后，可能出现一条到顶点的新的特殊路，如果这条新特殊路是先经过老的S到达顶点u,然后从u经过一条边直接到达顶点i，则这种路的最短长度是dist[u]+c[u][i]。如果dist[u]+c[u][i]dist[i]，则需要更新dist[i]的值。实验步骤(1)用带权的邻接矩阵c来表示带权有向图,c[i][j]表示弧vi,vj上的权值。设S为已知最短路径的终点的集合,它的初始状态为空集。从源点v经过S到图上其余各点vi的当前最短路径长度的初值为：dist[i]=c[v][i],vi属于V.(2)选择vu,使得dist[u]=Min{dist[i]|vi属于V-S},vj就是长度最短的最短路径的终点。令S=SU{u}.(3)修改从v到集合V-S上任一顶点vi的当前最短路径长度:如果dist[u]+c[u][j]dist[j]则修改dist[j]=dist[u]+c[u][j].(4)重复操作(2),(3)共n-1次.关键代码//4d5贪心算法单源最短路径问题#includeiostream#includefstream#includestringusingnamespacestd;constintN=5;constintM=1000;ifstreamfin(4d5.txt);templateclassTypevoidDijkstra(intn,intv,Typedist[],intprev[],Typec[][N+1]);voidTraceback(intv,inti,intprev[]);//输出最短路径v源点，i终点intmain(){intv=1;//源点为1intdist[N+1],prev[N+1],c[N+1][N+1];cout有向图权的矩阵为：endl;for(inti=1;i=N;i++){for(intj=1;j=N;j++){finc[i][j];coutc[i][j];}coutendl;}Dijkstra(N,v,dist,prev,c);for(inti=2;i=N;i++){cout源点1到点i的最短路径长度为:dist[i]，其路径为;Traceback(1,i,prev);coutendl;}return0;}templateclassTypevoidDijkstra(intn,intv,Typedist[],intprev[],Typec[][N+1]){bools[N+1];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的最短路径i的前一个顶点}else{prev[i]=v;}}dist[v]=0;s[v]=true;for(inti=1;in;i++){inttemp=M;intu=v;//上一顶点//取出V-S中具有最短特殊路径长度的顶点ufor(intj=1;j=n;j++){if((!s[j])&&(dist[j]temp)){u=j;temp=dist[j];}}s[u]=true;//根据作出的贪心选择更新Dist值for(intj=1;j=n;j++){if((!s[j])&&(c[u][j]M)){Typenewdist=dist[u]+c[u][j];if(newdistdist[j]){dist[j]=newdist;prev[j]=u;}}}}}//输出最短路径v源点，i终点voidTraceback(intv,inti,intprev[]){if(v==i){couti;return;}Traceback(v,prev[i],prev);cout-i;}测试结果实验心得此次实验让我对贪心算法的思想有了初步的了解，并且学会了用贪心算法解决一些实际问题。两个程序中都运用了循环语句，在编写代附录：完整代码//4d5贪心算法单源最短路径问题#includeiostream#includefstream#includestringusingnamespacestd;constintN=5;constintM=1000;ifstreamfin(4d5.txt);templateclassTypevoidDijkstra(intn,intv,Typedist[],intprev[],Typec[][N+1]);voidTraceback(intv,inti,intprev[]);//输出最短路径v源点，i终点码时，在循环语句的设置中遇到许多问题，经过调试最终解决。所以，以后应当多做一些循环语句的练习。通过实践加强编程的熟练程度。实验得分助教签名intmain(){intv=1;//源点为1intdist[N+1],prev[N+1],c[N+1][N+1];cout有向图权的矩阵为：endl;for(inti=1;i=N;i++){for(intj=1;j=N;j++){finc[i][j];coutc[i][j];}coutendl;}Dijkstra(N,v,dist,prev,c);for(inti=2;i=N;i++){cout源点1到点i的最短路径长度为:dist[i]，其路径为;Traceback(1,i,prev);coutendl;}return0;}templateclassTypevoidDijkstra(intn,intv,Typedist[],intprev[],Typec[][N+1]){bools[N+1];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的最短路径i的前一个顶点}else{prev[i]=v;}}dist[v]=0;s[v]=true;for(inti=1;in;i++){inttemp=M;intu=v;//上一顶点//取出V-S中具有最短特殊路径长度的顶点ufor(intj=1;j=n;j++){if((!s[j])&&(dist[j]temp)){u=j;temp=dist[j];}}s[u]=true;//根据作出的贪心选择更新Dist值for(intj=1;j=n;j++){if((!s[j])&&(c[u][j]M)){Typenewdist=dist[u]+c[u][j];if(newdistdist[j]){dist[j]=newdist;prev[j]=u;}}}}}//输出最短路径v源点，i终点voidTraceback(intv,inti,intprev[]){if(v==i){couti;return;}Traceback(v,prev[i],prev);cout-i;}