第4章j交通规划 算例
- 格式:doc
- 大小:176.50 KB
- 文档页数:16
【例题4-1】用Dijkstra法计算下图4-1所示路网从节点1到节点9的最短径路。
⑦⑧⑨
图4-1 交通网络示意图
【解】:
步骤1给定起点1的P标号:P[1]=0,其他节点标上T标号:T 1(2)=… = T 1 (9)= ∞。
步骤2 节点1 刚得到P标号。节点2、4与1相邻,且均为T标号,修改这两点的T标号:
T 2 (2)=min[T 1 (2),P(1)+d 12 ]=min[∞,0+2]=2
T 2 (4)=min[T 1 (4),P(1)+d 14 ]=min[∞,0+2]=2
在所有(包括没修改的)T标号中,找出最小标号。2、4为最小,任选其一,如节点2,即P[2]= T 2 (2)=2。
步骤3 节点2 刚得到P标号。节点3、5与2相邻,且均为T标号,修改这两点的T标号:
T 3 (3)=min[T(3),P(2)+d 23 ]=min[∞,2+2]=4
T 3 (5)=min[T(5),P(2)+d 25 ]=min[∞,2+2]=4
在所有T标号(点3,4,5…9)中,节点4为最小,给节点4标上P 标号,即P[4]= T 2 (4)=2。
步骤4 节点4 刚得到P标号。节点5、7与4相邻,且为T标号,修改这两点的T标号:
T 4 (5)=min[T(5),P(4)+d 45 ]=min[4,2+1]=3
T 4 (7)=min[T(7),P(4)+d 47 ]=min[∞,2+2]=4
在所有T标号中,节点5为最小,给节点5标上P标号,即P[5]= T 4 (5)=3。
步骤5 节点5 刚得到P标号。节点6、8与5相邻,且为T标号,修改这两点的T标号:
T 5 (6)=min[T(6),P(5)+d 56 ]=min[∞,3+1]=4
T 5 (8)=min[T(8),P(5)+d 58 ]=min[∞,3+2]=5
在所有T标号中,节点3为最小,给节点3标上P标号,即P[3]=T 3 (3)=4。
步骤6 节点3 刚得到P标号。节点6与3相邻,且为T标号,修改6的T标号:
T 6 (6)=min[T(6),P(3)+d 36 ]=min[4,4+2]=4
在所有T标号中,节点6为最小,给节点6标上P标号,即P[6]=T 6 (6)=4。
步骤7 节点6 刚得到P标号。节点9与6相邻,且为T标号,修改9的T标号:
T 7 (9)=min[T(9),P(6)+d 69 ]=min[∞,4+2]=6
在所有T标号中,节点7为最小,给节点7标上P标号,即P[7]= T 4 (7)=4。
步骤8 节点7 刚得到P标号。节点8与7相邻,且为T标号,修改8的T标号:
T 8 (8)=min[T(8),P(7)+d 78 ]=min[5,4+2]=5
在所有T标号中,节点8为最小,给节点8标上P标号,即P[8]=T 8 (8)=5。
步骤9 节点8 刚得到P标号。节点9与8相邻,且为T标号,修改9的T标号:
T 9 (9)=min[T(9),P(8)+d 89 ]=min[6,5+2]=6
在所有T标号中,节点9为最小,给节点9标上P标号,即P[9]= T 9 (9)=6。
所有节点均标上了P标号,计算结束。得到节点1到其他各节点的最短路权(P标号)
表4-1 例题8-1计算结果
节点 1 2 3 4 5 6 7 8 9
1 0
2 4 2
3
4 4
5
6 P标号P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9)
【例题4-2】] 求解例题4.2 - 1网络任节点间的最短路权。
【解】:(1) 根据交通网络结构,距离矩阵表示如下。
表4-2 交通网络的距离矩阵
(2)进行矩阵迭代运算(第2步)
d212=min[d11+d12,d12+d22,d13+d32,d14+d42,d15+d52,d16+d62,d17+d 72,d18+d82,d19+d92]
=min[0+2,2+0,∞+2,2+∞,∞+2,∞+∞,∞+∞, ∞+∞, ∞+∞]=2 (i=1,j=2;k=1,2,…9)
d213、d214、d215…d219计算同理,如d215:
d215 =min[d11+d15 ,d12+d25 ,d13+d35 ,d14
+d45 ,d15+d55 ,d16+d65 ,d17+d75 ,d18+d85 ,d19+d95 ]
=min[0+∞,2+2,∞+∞,2+1,∞+0,∞+1,∞+∞,∞+2,∞+∞]=3 (i=1,j=5;k=1,2…9)
从节点1经过两步到达5的最短路权为3。其他元素按同样方法计算,得到D2
(3)进行矩阵迭代运算
经过三步到达某一节点的最短距离为:
D3 = D2~D=[d3ij ]
[d3ij ] =min[d2ik +d kj ] (k=1,2,3,…,n)
式中:d2ik— --- 距离矩阵D2中的元素;
d kj --- —距离矩阵D中的元素。
(4)进行矩阵迭代运算(第m步)
经过m 步到达某一节点的最短距离为:D m =D m-1~D=[d m ij ]
[d m ij ] =min[d m-1ik +d kj ] (k=1,2,3,…,n)
式中:d m-1ik— --- 距离矩阵D m-1中的元素;
d kj --- —距离矩阵D中的元素。
迭代不断进行,直到D m =D m-1。即D m中的每个元素等于D m-1中的每个元素为止,此时的D m便是任意两点之间的最短路权矩阵。