Dijkstra算法求一点到所有点的最短路径.doc

Dijkstra算法求一点到所有点的最短路径(2010-03-2523:22:01)转载▼标签:迪杰斯特拉求一点到所有点的最短路径dijkstrait分类:数据结构&算法设计与分析  //迪杰斯特拉求一点到所有点的最短路径-------------------------------------------------------------------------迪杰斯特拉求一点到所有点的最短路径(Dijkstra)算法描述1、选定起点放入E集合中。2、把未选点放入R集合中,写出E集合中所有点到R集合中所有点的路径放入Path集合(以“E中的点—R中的点=权值”为形式)。3、在Path中选择权值最小的路径,在Path中标*号(不参与下一次在Path中选择权值最小的路径),再放入S中。然后把这个路径中的从R中选出的点(路径中的终点)加入E,从R中移除。4、返回2到3进行循环,直到R为空,就到55、S集合中就是起点到其他点的最短路径。---------------------------------------------------------------------------表格演示:E(已选点)R(未选点)Path(路径)S(选中路径)01,2,3,4*0-1=10-2=30-3=∞0-4=∞0-1=10,12,3,40-1-2=∞0-1-3=1+4=50-1-4=∞*0-2=30-3=∞0-4=∞0-2=30,1,23,40-2-3=3+2=50-2-4=3+2=50-1-2=∞*0-1-3=1+4=50-1-4=∞0-3=∞0-4=∞0-1-3=1+4=50,1,2,340-1-3-4=1+4+1=60-2-4=3+2=5*0-2-4=3+2=50-2-3=3+2=50-1-2=∞0-1-4=∞0-3=∞0-4=∞    ------------------------------------------------------------------------------------------//////////////////////////////////////代码实现程序结构:---------------------------------------------------------------------------------------------最终生成的树结构转化为以下的表结构:(在代码中对应的是Tree数组)id0123344root0001223right99135556flag011111          id:到达的点。root:是id中对应的根。right:是id所对应的权值加上其root的权值。注,其表生成时是从左往右的,故权值是可以累加的。flag:在算法描述中的*号标记。----------------------------------------------------------------------------------------------res数组实现算法描述中的ER集合(最终生成的在代码中对应的res数组表)resid   01234flag21111注:起点flag标记为2-----------------------------------------------------------------------------------------------//结果使用递归打印//4<-2<-0//3<-2<-0//3<-1<-0//2<-0//1<-0----------------------------------------------------------------------------------------------//Java代码//classTree{intid=0;introot=0;intright=0;intflag=0;publicvoidsetAll(intid,intro,intri,intfl){=fl;=id;=ri;=ro;}publicvoidsetFlag(intflag){=flag;}publicvoidsetId(intid){=id;}publicvoidsetRight(intright){=right;}publicvoidsetRoot(introot){=root;}publicvoidget_r(Treet){=;=;=;=;}p