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

1、Dijkstra算法求一点到所有点的最短路径原文地址：Dijkstra算法求一点到所有点的最短路径作者：沐早的笔记本/迪杰斯特拉求一点到所有点的最短路径-迪杰斯特拉求一点到所有点的最短路径(Dijkstra)算法描述1、选定起点放入E集合中。2、把未选点放入R集合中，写出E集合中所有点到R集合中所有点的路径放入Path集合(以"E中的点-R中的点=权值"为形式)。3、在Path中选择权值最小的路径，在Path中标*号(不参与下一次在Path中选择权值最小的路径)，再放入S中。然后把这个路径中的从R中选出的点(路径中的终点)加入E，从R中移除。4、返回2到3进行循环，直到R为

2、空，就到5 5、S集合中就是起点到其他点的最短路径。-表格演示：E(已选点)R(未选点)Path(路径)S(选中路径)01，2，3，4*0-1=1 0-2=3 0-3=0-4=0-1=1 0，12，3，40-1-2=0-1-3=1+4=5 0-1-4=*0-2=3 0-3=0-4=0-2=3 0，1，23，40-2-3=3+2=5 0-2-4=3+2=5 0-1-2=*0-1-3=1+4=5 0-1-4=0-3=0-4=0-1-3=1+4=5 0，1，2，340-1-3-4=1+4+1=6*0-2-4=3+2=5 0-2-3=3+2=5 0-1-2=0-1-4=0-3=0-4=0-2-4=3+

3、2=5-/代码实现程序结构：-最终生成的树结构转化为以下的表结构：(在代码中对应的是Tree数组)id 0123344 root 0001223 right 99135556 flag 011111 id：到达的点。root：是id中对应的根。right：是id所对应的权值加上其root的权值。注，其表生成时是从左往右的，故权值是可以累加的。flag：在算法描述中的*号标记。-res数组实现算法描述中的E R集合(最终生成的在代码中对应的res数组表)res id 01 23 4flag 21 11 1注：起点flag标记为2-/结果使用递归打印/4-2-0/3-2-0/3-1-0/2-0/1

4、-0-/Java代码/class Treeint id=0；int root=0；int right=0；int flag=0；public void setAll(int id,int ro,int ri,int fl)this.flag=fl；this.id=id；this.right=ri；this.root=ro；public void setFlag(int flag)this.flag=flag；public void setId(int id)this.id=id；public void setRight(int right)this.right=right；public voi

5、d setRoot(int root)this.root=root；public void get_r(Tree t)this.flag=t.flag；this.id=t.id；this.right=t.right；this.root=t.root；public boolean equals(Tree t)if(this.flag=t.flag)&&(this.id=t.id)&&(this.right=t.right)&&(this.root=t.root)return true；elsereturn false；public boolean

6、isZero()if(this.flag=0)&&(this.id=0)&&(this.right=0)&&(this.root=0)return true；elsereturn false；class RESetint id=0；int flag=0；public void setId(int id)this.id=id；public void setFlag(int flag)this.flag=flag；public class DijkstraFindRoadstatic int node=/0,1,2,3,499,1,3,99,99,1

7、,99,99,4,99,3,99,99,2,2,99,4,2,99,1,99,99,2,1,99；public DijkstraFindRoad()public static int printRoad(Tree t,int i)/打印路径System.out.print("-"+tgetRtNum_r(t,ti).id)；if(ti.right=99)return 0；elseprintRoad(t,getRtNum_r(t,tgetRtNum_r(t,ti)；return 1；public static void removeSameValue(Tree tq)/去除重

8、复int flag=0,j=0；for(int i=0；i tq.length；i+)for(j=0；j tq.length；j+)if(tqi.equals(tqj)&&(！tqi.isZero()flag=i；tqflag.setAll(0,0,0,0)；public static int getRtNum_r(Tree tq,Tree t)/取得t的根的物理地址int rti=0；for(int i=0；i tq.length；i+)if(t.root=tqi.id)rti=i；break；return rti；public static boolean isRoadFu

9、ll(Tree t,RESet rs)/是否所有路径都已选择int counter=0；for(int i=1；i t.length；i+)if(ti.flag=1)counter+；if(rs.length=counter)return true；return false；public static void main(String args)Tree t=new Tree20；Tree temp=new Tree()；/做交换用RESet res=new RESet5；int start=0；/指定起点，从0点开始/初始化for(int i=0；i res.length；i+)resi=n

10、ew RESet()；resi.setId(i)；for(int i=0；i t.length；i+)ti=new Tree()；resstart.setFlag(2)；t0.setId(start)；t0.setRoot(0)；t0.setRight(99)；t0.setFlag(0)；/int ti=1；int j=0；int xi=0,yj=0,counter=0；ti=1；while(true)/yj=0；for(int i=0；i res.length；i+)if(resi.flag=0)yj+；xi=res.length-yj；/System.out.println("x

11、i："+xi+""+"yj："+yj+"|ti："+ti)；/选取点操作int ii=xi-1,nbeg=ti,nend=0；for(j=xi-1；j res.length；j+)/1 if(nodeiij！=99)/if tti.setId(j)；tti.setRoot(ii)；tti.setRight(nodeiij)；ti+；/if/1 nend=ti；/加权操作/System.out.println("ROOT："+getRtNum_r(t,t4)；for(int i=nbeg；i nend；i+

12、)if(ti.root！=0)ti.setRight(tgetRtNum_r(t,ti).right+ti.right)；/选最小权值int min=99；int f=0；for(int i=0；i t.length；i+)if(ti.right！=0)&&(ti.flag！=1)&&(ti.right min)min=ti.right；f=i；/选最小权值，做标记tf.setFlag(1)；restf.id.flag=1；/System.out.println("11111："+tf.id+"："+tf.root+"："+tf.right+"："+tf.flag)；/if(isRoadFull(t,res)break；/removeSameValue(t)；/for(int si=0；si res.length；si+)/System.out.println(ressi.id+"："+ressi.flag)；/for(int si=0；si t.length；si+)/System.out.p