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

Dijkstra算法求一点到所有点的最短路径
  (2010-03-25 23:22:01)
转载▼
标签: 
迪杰斯特拉
 
求一点
 
到所有点的
 
最短路径
 
dijkstra
 
it
分类: 数据结构&算法设计与分析
//迪杰斯特拉求一点到所有点的最短路径
-------------------------------------------------------------------------
迪杰斯特拉求一点到所有点的最短路径(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(选中路径)
0
1,2,3,4
*0-1=1
0-2=3
0-3=∞
0-1=1
0-4=∞
0,1
2,3,4
0-1-2=∞
0-1-3=1+4=5
0-1-4=∞
*0-2=3
0-3=∞
0-4=∞
0-2=3
0,1,2
3,4
0-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,3
4
0-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
0
1
2
3
3
4
4
 
 
root
0
0
0
1
2
2
3
 
 
right
99
1
3
5
5
5
6
 
 
flag
0
1
1
1
1
1
 
 
 
 
id:到达的点。
root:是id中对应的根。
right:是id所对应的权值加上其root的权值。