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

《用贪心算法解单源最短路径问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、广东金融学院实验报告课程名称：算法设计与分析课程设计实验编号及实验名称实验六用贪心算法解单源最短路径问题系别应用数学系姓名许夏梦学号071612117班级0716121实验地点新电605实验日期2009-11-4实验时数4指导教师骆世广同组其他成员独立完成成绩一、实验目的及要求1、明确单源最短路径问题的概念；2、用贪心算法解决单源最短路径问题；3、通过本例熟悉贪心算法在程序设计中的应用方法。二、实验环境及相关情况（包含使用软件、实验设备、主要仪器及材料等）使用软件：C++软件；使用实验设备：计算机：Intel（R）;Pentium（R）4CPU2.

2、80GHz;2.79GHz,0.99GB的内存；使用系统：MicrosoftWindowsXP;Professional;版本2002；ServicePack2.三、实验内容及步骤（包含简要的实骑步骤流程）实验内容：求网（带权有向图）屮从一个顶点到其余各顶点间的最短路径。一个有向图G,它的每条边都有一个非负的权值c[i,j],“路径长度"就是所经过的所有边的权值之和。对于源点需要找出从源点出发到达其他所有结点的最短路径。■

3、BZ5-aUX.X3A>・A・五号・刃贴!SQ

4、：=・

5、=・•计潭淒Xr

6、■・■■it:=•■IM*>r；FilesMicro

7、softVisualStudioMyProjects11Debu<11.mc*from1to2fth©shortestwayis45far：2<**■4

8、x•・11"

9、iieroc*CPro(raAaBI鱼ec1見改样式3Hicroso...•S}Uicroioft石单Q劝可1四、实验结果（包括程序或图表、结论陈述、数据记录及分析等，可附页）如下图所示，编程实现求从任一顶点出发到其它顶点的最短路径长度。（图见附录四-1）实验结果如下（程序见附录四-2）：入戻聞希用引用邻件3?闻進Pleaseinputnumberofpoint:6Nowinputlengthitoj：oseiee45ooo15e1Go26ge15oo020ee35G0003605000366Nouinputupoint(0

10、:1五、实验总结（包括心得体会、问题回答及实验改进意见，可附页）通过在计算机实现用贪心算法解单源最短路径问题，对贪心算法有了更进一步的理解。“学精于勤而荒于嬉”，在专业技能上还需多学、多看、多练，实践是不断取得进步的基础。我要通过实践不断的锻炼自己，提高自己解决实际问题的能力。六、教师评语附四-1附四-2程序代码：#inelude#include〈conio.h>intn=0,/*结点个数*/prev[100],/*记录最短路径到i的前一个顶点*/s[101];floata[100][100],/*记录边的权值*/dist[100

11、];/*记录从源点到i的相应最短路径*/#defineMAXVALUE100000.0voiddijkstra(intv){inti,j;if(v

12、

13、v>n)return;for(i=l;i<=n;i++)/*初始设置*/{/*初始时从源点到i的最短路径设为从源点到i的权值*/s[i]=l;/*s[i]二false*/if(dist[i]==MAXVALUE)prev[i]=0;/*从源点到i没有通路*/elseprev[i]=v;/*从源点到i有通路时，最短路径前一个结点设为源点*/}dist[v]=O;/*源点到源点的最短路径为0*/s[v

14、]二0;/*s[v]二true*//*为卜•面循环中源点不参加比较做准备*/for(i=l;i

15、j++)/*找出通过U点是否有更短的路径*/if((s[j]==l)&&(a[u][j]