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

Dijkstra算法求一点到所有点的最短路径
原文地址:Dijkstra算法求一点到所有点的最短路径作者:沐早的笔记本//迪杰斯特拉求一点到所有点的最短路径
---
迪杰斯特拉求一点到所有点的最短路径(Dijkstra)算法描述
1、选定起点放入E集合中。
2、把未选点放入R集合中,写出E集合中所有点到R集合中所有点的路径放入Path集合(以"E中的点-R中的点=权值"为形式)。
3、在Path中选择权值最小的路径,在Path中标*号(不参与下一次在Path中选择权值最小的路径),再放入S中。然后把这个路径中的从R中选出的点(路径中的终点)加入E,从R中移除。
4、返回2到3进行循环,直到R为空,就到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+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 4
flag 21 11 1
注:起点flag标记为2
---
//结果使用递归打印
//4-2-0
//3-2-0
//3-1-0
//2-0
//1-0
--
//Java代码//
class Tree{
int id=0;
int root=0;
int right=0;
int flag=0;
public void setAll(int id,int ro,int ri,int fl){
=fl;
=id;
=ri;
=ro;
}
public void setFlag(int flag){
=flag;
}
public void setId(int id){
=id;
}
public void setRight(int right){
=right;
}
public void setRoot(int root){
=root;
}
public void get_r(Tree t){
=;
=;
=;
=;
}
public boolean equals(Tree t){
if((==)&&(==)&&(==)&&(==)){
return true;
}else{
return false;
}
}
public boolean isZero(){
if((==0)&&(==0)&&(==0)&&(==0)){
return true;
}else{
return false;
}
}
}
class RESet{
int id=0;
int flag=0;
public void setId(int id){
=id;
}
public void setFlag(int flag){
=flag;
}
}
public c