dijkstra算法求一点到所有点的最短路径

《dijkstra算法求一点到所有点的最短路径》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Dijkstra算法求一点到所有点的最短路径 (2010-03-2523:22:01)转载▼标签： 迪杰斯特拉 求一点 到所有点的 最短路径 dijkstra it分类： 数据结构&算法设计与分析//迪杰斯特拉求一点到所有点的最短路径-------------------------------------------------------------------------迪杰斯特拉求一点到所有点的最短路径（Dijkstra）算法描述1、选定起点放入E集合中。2、把未选点放入R集合中，写出E集合中所有点到R集合中所有点的

2、路径放入Path集合（以“E中的点—R中的点=权值”为形式）。3、在Path中选择权值最小的路径，在Path中标*号（不参与下一次在Path中选择权值最小的路径），再放入S中。然后把这个路径中的从R中选出的点（路径中的终点）加入E，从R中移除。4、返回2到3进行循环，直到R为空，就到55、S集合中就是起点到其他点的最短路径。---------------------------------------------------------------------------表格演示： E（已选点）R（未选点）Path（路径）S

3、（选中路径）01，2，3，4*0-1=10-2=30-3=∞0-1=10-4=∞0，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=6*0-2-4=3+2=50-2-3=3+2=50-1-2=∞0-1-4=∞0-3=∞0-4=∞0-2-4=3+2=5      -------

4、-----------------------------------------------------------------------------------//////////////////////////////////////代码实现程序结构：---------------------------------------------------------------------------------------------最终生成的树结构转化为以下的表结构：（在代码中对应的是Tree数组） id01233

5、44  root0001223  right99135556  flag011111    id：到达的点。root：是id中对应的根。right：是id所对应的权值加上其root的权值。注，其表生成时是从左往右的，故权值是可以累加的。flag：在算法描述中的*号标记。----------------------------------------------------------------------------------------------res数组实现算法描述中的ER集合（最终生成的在代码中对应的res数组表

6、）resid   01234flag21111注：起点flag标记为2-----------------------------------------------------------------------------------------------//结果使用递归打印//4<-2<-0//3<-2<-0//3<-1<-0//2<-0//1<-0--------------------------------------------------------------------------------------

7、--------//Java代码//classTree{ intid=0; introot=0; intright=0; intflag=0; publicvoidsetAll(intid,intro,intri,intfl){  this.flag=fl;        this.id=id;        this.right=ri;        this.root=ro; } publicvoidsetFlag(intflag){  this.flag=flag; } publicvoidsetId(intid){ 

8、 this.id=id; } publicvoidsetRight(intright){  this.right=right; } publicvoidsetRoot(introot){  this.root=root; } publicvoidget_r(Treet){     this