用贪心算法解单源最短路径问题.docx

广东金融学院实验报告课程名称：算法设计与分析课程设计实验编号及实验名称实验六 用贪心算法解单源最短路径问题系 别应用数学系姓 名许夏梦学 号071612117班级0716121实验地点新电605实验日期2009-11-4实验时数4指导教师骆世广同组其他成员独立完成成绩一、 实验目的及要求1、明确单源最短路径问题的概念；2、用贪心算法解决单源最短路径问题；3、通过本例熟悉贪心算法在程序设计中的应用方法。二、 实验环境及相关情况（包含使用软件、实验设备、主要仪器及材料等）使用软件：C+软件；使用实验设备：计算机：Intel(R);Pentium(R) 4 CPU 2.80GHz;2.79 GHz,0.99 GB 的内存；使用系统：Microsoft Windows XP;Professional;版本 2002；Service Pack 2.三、 实验内容及步骤（包含简要的实验步骤流程）实验内容：求网（带权有向图）中从一个顶点到其余各顶点间的最短路径。一个有向图G，它的每条边都有一个非负的权值ci,j，“路径长度”就是所经过的所有边的权值之和。对于源点需要找出从源点出发到达其他所有结点的最短路径。四、 实验结果（包括程序或图表、结论陈述、数据记录及分析等，可附页）如下图所示，编程实现求从任一顶点出发到其它顶点的最短路径长度。（图见附录四-1）实验结果如下（程序见附录四-2）：五、 实验总结（包括心得体会、问题回答及实验改进意见，可附页） 通过在计算机实现用贪心算法解单源最短路径问题，对贪心算法有了更进一步的理解。“学精于勤而荒于嬉”，在专业技能上还需多学、多看、多练，实践是不断取得进步的基础。我要通过实践不断的锻炼自己，提高自己解决实际问题的能力。六、 教师评语附四-1附四-2程序代码：#include #include int n=0, /*结点个数*/prev100, /*记录最短路径到i的前一个顶点*/s101;float a100100, /*记录边的权值*/dist100; /*记录从源点到i的相应最短路径*/#define MAX_VALUE 100000.0void dijkstra(int v) int i,j; if(vn) return; for(i=1;i=n;i+)/*初始设置*/ disti=avi; /*初始时从源点到i的最短路径设为从源点到i的权值*/ si=1; /*si=false*/ if(disti=MAX_VALUE) previ=0; /*从源点到i没有通路*/ else previ=v; /*从源点到i有通路时，最短路径前一个结点设为源点*/ distv=0; /*源点到源点的最短路径为0*/ sv=0; /*sv=true*/ /*为下面循环中源点不参加比较做准备*/ for(i=1;in;i+)/*中心部分*/ float temp=MAX_VALUE; int u=v; for(j=1;j=n;j+)/*找出一个剩余结点中到源点最短的结点*/ if(sj=1) & (distjtemp) /*如果该点不是源点并且源点到j点路径是最短*/ u=j; /*u记录最短路径的点*/ temp=distj; /*记录源点到j点的最短路径*/ su=0; /*su=true*/ /*u点是下面进行比较的点*/ for(j=1;j=n;j+)/*找出通过U点是否有更短的路径*/ if(sj=1) & (aujMAX_VALUE) float newdist=distu+auj; if(newdistdistj) /*源点到u的路径+u到j的路径源点到j的路径*/ distj=newdist; /*更改源点到j的路径长度*/ prevj=u; /*更改源点到j的最短路径中，j的前一个结点*/ main() int i,j,v; float temp; printf(Please input number of point:n); scanf(%d,&n); /*输入结点的个数*/ printf(Now input length i to j:n); for(i=1;i=n;i+) for(j=1;jj的权值*/ if(aij=0.0) aij=MAX_VALUE; /*输入为0表示没有通路，改为最大值*/ if(i=j) aij=0.0; /*i-i的权值为0*/ printf(Now input v point(0point=%d):n,n); scanf(%d,&v); /*输入起始结点*/ dijkstra(v); printf(-n); for(i=1;i=n;i+)/*设置输出*/ if(i!=v & distiMAX_VALUE) /*源点到源点；源点到某点最长路径为无穷大的都不需要输出*/ printf(nfrom %d to %d,the shortest way is %g far:n%d,v,i,d