图48用 Dijkstra算法求最短路径的网络举例 解:表41是对题图48所给网络按照 Dijkstra算法进行求解的详细步骤。 表41计算图48网络的最短路径 「步骤 C(2 C (4) C(5) C(6) 初始化 1,4} 222 5433 4 2345 1,2,45} (2) 2 (3) 4 1,2,3,4,56} (4) 初始化:因为选择了节点1为源节点,因此一开始在集合M中只有节点1。节点 1只与节点2、3和4直接相连,因此在初始化时,在C(2),C(3)和C(4)下面就填入节 点1到这些节点相应的距离,在C5)和C(6)下面填入∞。 步骤1:在节点1以外的节点中,找出一个距节点1最近的节点w,这应当是w=4 因为在C(2),C(3)和C(4)中,C(4)=1,它的权值最小。于是将节点4加入到节点集合 M中。这时,在步骤1这一行和C(4)这一列相交处填写(1),数字1表示节点4到节点 1的距离,数字1的括号表示节点4在这个步骤加入到节点集合M中了。 接着就要对所有不在集合M中的节点(即节点2、3、5和6)逐个执行: C(n):=Min(C(n), c(w)+ len(w, n) 对于节点2,原来的C(2)=2。现在C(w)+en(w,n)=C(4)+len(4,2)=1+2=3>C(2) 因此节点2到节点1距离不变,仍为2。 对于节点3,原来的C(3)=5。现在C(w)+en(w,n)=C(4)+len(4,3)=1+3=4<C(3) 因此节点3到节点1的距离要更新,从5减小到4。 对于节点5,原来的C(5)=∞。现在Cw)+len(w,n=C(4)+en(4,5)=1+1=2<C(5)图 4.8 用 Dijkstra 算法求最短路径的网络举例 解：表 4.1 是对题图 4.8 所给网络按照 Dijkstra 算法进行求解的详细步骤。 表 4.1 计算图 4.8 网络的最短路径 步骤 M C2 C3 C4 C5 C6 初始化 {1} 2 5 1   1 {1,4} 2 4 （1） 2  2 {1,4,5} 2 3 1 （2） 4 3 {1,2,4,5} （2） 3 1 2 4 4 {1,2,3,4,5} 2 （3） 1 2 4 5 {1,2,3,4,5,6} 2 3 1 2 （4） 初始化：因为选择了节点 1 为源节点，因此一开始在集合 M 中只有节点 1。节点 1 只与节点 2、3 和 4 直接相连，因此在初始化时，在C2，C3和C  4 下面就填入节 点 1 到这些节点相应的距离，在C5和C6下面填入。 步骤 1：在节点 1 以外的节点中，找出一个距节点 1 最近的节点 w，这应当是 w=4， 因为在C  2 ，C  3 和C  4 中，C  4  1，它的权值最小。于是将节点 4 加入到节点集合 M 中。这时，在步骤 1 这一行和C4这一列相交处填写（1），数字 1 表示节点 4 到节点 1 的距离，数字 1 的括号表示节点 4 在这个步骤加入到节点集合 M 中了。 接着就要对所有不在集合 M 中的节点（即节点 2、3、5 和 6）逐个执行： C  n ：= Min  C     n ,C w  len w,n 。 对于节点 2，原来的C  2  2 。现在 C（w）+len(w，n)=C（4）+len（4，2）=1+2=3>C(2)。 因此节点 2 到节点 1 距离不变，仍为 2。 对于节点 3，原来的C  3  5。现在 C(w)+len(w，n)=C(4)+len（4，3）=1+3=4<C(3)。 因此节点 3 到节点 1 的距离要更新，从 5 减小到 4。 对于节点 5，原来的C  5   。现在 C(w)+len(w，n)=C(4)+len（4，5）=1+1=2<C(5)