 |
| |
 前一页 |
后一页 |
 |
 |
|
路径选择 |
二、最短路径选择算法
原理：求最短路径可以从网络中任一点（该点作源结点）出发，找出与其相邻结点中最短的通路，再以该点出发继续找与它相邻结点的最短路，直至找完全部结点为止。
方法：建立一个节点集N,再计算新结点与其相邻点距离。选最短路的节点加入N集，直至结点全部包含在N集内为止。
算法步骤：
（1）初始化，建立集合N,开始仅包含源结点s在内。标与其它结点的距离，若i结点与s相邻，则i,s的路长D(i)=∞。
（2）找出N集的相邻且D值最小的结点j,结点j加入N集，对N集外的其他结点进行更新标数值计算，即
D(i)新=Min[D(i)老，D(j)+l(j,i)]
直至网内全部结点都包含在N集为止。比较各步中各结点到源结点的距离取其最短者。
eg.求图3.4-3(a)中，源点1到其他结点的最短路径。
初始化：源点至其它结点间距离为
N D(2) D(3) D(4) D(5) D(6)
[1] 2 5 1 ∞ ∞
计算：
因为D(4)=1,最小，故结点4放于N中，重新标距离。
D(2)新=MIN[D(2)老，D(4)+l(4,2)]=MIN(2,1+2)=2
D(3)新=MIN[D(3)老，D(4)+l(4,3)]=MIN(5,1+3)=4
D(5)新=MIN[D(5)老，D(4)+l(4,5)]=MIN( ,1+1)=2
D(6)新=MIN[D(6)老，D(4)+l(4,6)]=MIN( ,1+ )=∞
得 N D(2) D(3) D(4) D(5) D(6)
[1，4] 2 5 1 2 ∞
将结点2，5，放入N中，进行重新计算，并标值，以后逐步将3，6放入N中。
|
|
|
|
|
|
