单源点最短路径问题.doc

《单源点最短路径问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法设计与分析》实验报告实验名称：单源点最短路径问题任课教师：专业：学号：姓名：完成日期：2013.12.20成绩：________________一、实验目的：找出一个有向图中起点到其余各点之间的最短路，并得出最短路的大小二、实验内容：单源点最短路径问题，即已知一个n结点有向图G＝（V,E）和边的权函数c（e），求由某指定结点V0到其他各个结点的最短路径，这里还假定所有的权都是正的，本实验要求输出最短路径值以及最短路径。三、程序设计说明：(算法设计思路)建立一个集合S，开始时初始化为空，在图中，将第一个点的最小距离估计值定义为

2、0，其他的定义为最大值，先将第一个点移到S中，然后更新与第一点相连的各点的距离估计值。然后再找最小距离估计值的点，移到S中，再重复更新，如此循环,就能得到从起点到其他各点的最短路大小。新建一个一维数组，数组中存放着到达每个点的前一个点，从后往前搜索，就可以得到到各点的路径。四、程序代码（经调试正确的源程序）usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;namespacedijkstra3{//再次来尝试，前两次失败是因为整

3、体思路不明晰和数组溢出，这次再重新尝试一下//classProgram{staticintN=6;staticintMAX=1000;staticint[,]w=newint[7,7]{{0,0,0,0,0,0,0},{0,0,1,12,MAX,MAX,MAX},{0,MAX,0,9,3,MAX,MAX},{0,MAX,MAX,0,MAX,5,MAX},{0,MAX,MAX,4,0,13,15},{0,MAX,MAX,MAX,MAX,0,4},{0,MAX,MAX,MAX,MAX,MAX,0}};staticint[]d=newi

4、nt[N+1];staticint[]S=newint[7]{0,0,0,0,0,0,0};staticint[]a=newint[7];staticvoidMain(string[]args){inti;Dijkstra(1);Console.Write("从起点到其余各的最短路分别为点：");for(i=1;i<=N;i++){Console.Write(d[i]+"");}Console.WriteLine();for(inta=0;a<=N;a++){Console.Write("起点到{0}点的路径",a);if(a>=

5、1&&a<=N){Console.Write(a);if(a>1){Console.Write("《");}output(a);}Console.WriteLine();}Console.ReadKey();}staticvoidoutput(intx){if(a[x]<=N){intf=a[x];Console.Write(f);if(f>1)Console.Write("《");output(f);}}staticintextract_min(){intu=0;inti;for(i=1;i<=N;i++){if(S[i]==0

6、&&d[i]d[u]+w[u,v]){d[v]=d[u]+w[u,v];a[v]=u;}}}}}}}五．程序运行结果（测试数据和运行结果）六、算法复杂性分析（对所编

7、写程序的时间复杂性和空间复杂性的分析）T(n)=θ()七、实验中遇到的问题及解决方法八、实验总结注：实验报告填写时，注意输入信息的字体格式（宋体、五号），如果用复制应采用选择性粘贴的“无格式文本”方法完成；“程序运行结果”请以屏幕拷贝的方式将运行结果的截图复制在报告中。