单源点最短路径问题

算法设计与分析如实报告实验名称：单一来源点最短路径问题教师：全职：学号：声明：完成日期：2013.12.20完成情况：_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ u首先，实验目的：找出直接图的起点和其馀点之间的最短路径，导出最短大小2、实验内容：如果单个源点最短路径问题，即n节点使用图形g=(v，e)和边的权重函数c(e)查找从给定节点V0到其他每个节点的最短路径，则此处的所有权重都假定为正。此实验要求输出最短路径值和最短路径。3、编程说明： (算法设计思想)创建集s，初始设置为空，将地物中第一个点的最小距离估计定义为0，将其他定义为最大值，将第一个点移动到s，然后更新连接到第一个点的每个点的距离估计。然后，找到最小距离估计的点，移动到s并再次更新，以获得从起点到其他点的最短大小。通过创建带有到达每个点之前的上一个点的一维阵列，然后从后面向前搜索，可以得到每个点的路径。4、程序代码(正确的源程序调试)Using Systemusing system . collections . generic；Using System。LinqUsing System。TextNamespace dijkstra3/请重试。前两次失败是因为整个想法不明确，数组溢出。这次再试一次/类程序static int N=6；Static int MAX=1000Static int， w=new int7，7 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，0，4，0，max，max，max，max，max，0static intd=new intN 1；Static int s=new int 7 0，0，0，0，0 ；static inta=new int7；Static void Main(string args)int I；Dijkstra(1)；控制台。Write(从起点到其馀段落各点：)；for(I=1)；I=N；I)控制台。写入(dI)；控制台。WriteLine()；for(int a=0)；a=N；a)控制台。Write(“从起点到点的路径”，a)；If (a=1 a=N)控制台。写入(a)；If (a 1)控制台。write(“”)；输出(a)；控制台。WriteLine()；控制台。read key()；Static void output(int x)If (ax=N)int f=ax；控制台。写入(f)；If(f1)控制台。write(“”)；输出(f)；Static int extract_min()int u=0；int I；for(I=1)；I=N；I)If (Si=0 di du wu，v)Dv=du wu，v；av=u；5.程序运行结果(测试数据和运行结果)6、算法复杂性分析(分析编写程序的时间复杂性和空间复杂性)T(n)=()7、实验中面临的问题和解决方法八、实验摘要附注：编写实验报告时，