2020/8/2
邓建华
1． Dijkstra法（标号法）
(2)算法步骤
Step2 设经过了K-1）步标号，节点i是刚得到P标号 的点，则对所有没有得到P标号的点进行下一步新的标 号（第K步）；考虑所有与节点i相邻且没有标上P标号 的点{j}，修改它们的T标号：
T kj m in [T j,P (i) d ij]
2020/8/2
邓建华
1． Dijkstra法（标号法）
(1) 算法思想 ①首先从起点O开始，给每个节点一个标号,分为T标号
和P标号两类； T是临时标号，表示从起点O到该点的最短路权上限； P标号是固定标号，表示从起点O到该点的最短路权。 ②标号过程中，T标号一直在改变，P标号不再改变，
凡是没有标上P标号的点，都标上T标号。 ③算法的每一步把某一点的T标号改变为P标号，直到
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。
所有节点均标上了 P标号，计算结束。得到节点1到 其他各节点的最短路权（P标号） 表 8.2-1 例题8-1计算结果
城市道路：可以计算分流向的、不分流的 交通流的延误，但是在实际操 作中比较困难，所以也可忽略 不计，或简单估计。
2020/8/2
邓建华
三、径路与最短径路
（一）径路与最短径路的定义
路段 网络上相邻两个节点之间的交通线路。
径路 网络上任意一OD点对之间，从发生点到吸引 点一串连通的路段的有序排列叫做这一OD点 对之间的径路。一OD点对之间可有多条径路。
式中 d ij— i到j的距离（路权）； T(j ) —第K步标号前j点的T标号。
2020/8/2
邓建华
1． Dijkstra法（标号法）
(2)算法步骤 在所有的T标号（包括没有被修改的）中，比选出最小 的T标号T k（j 0 ）：
T kj0m in [T kj,Tr]
式中 j 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]==min[∞ ,0+2]=2 在所有（包括没修改的）T标号中，找出最小标号。2、4为最小，任选其一，如 节点2，即P[2]= T 2 (2)=2。 步骤 3 节点2 刚得到P标号。节点3、5与2相邻，且均为T标号，修改这两点的T 标号：
•实际中路阻是常量还是变量？
•路径选择的随机性表现在哪些方面，在交通分配时
将会有何思路解决。
2020/8/2
邓建华
第二节 交通流分配中的基本概念
一、 交通分配 交通流分配涉及到以下几个方面:
可将现状OD交通量分配到现状交通网络上，以分 析目前交通网络的运行状况。
也可以是将规划年OD交通量分布预测值分配到 现 状交通网络上，以得到规划年交通需求，为交通网 络的规划设计提供依据。
T(r ) —与i点不相邻点r的T标号。
给点 j 0 标上P标号：P(j 0 ) =T k (j 0 )，第K步标号
结束。
Step3 当所有节点中已经没有T标号，算法结束，得到
从起点1到其他各点的最短路权；否则返回Step2 。
2020/8/2
邓建华
【例8－1】 步骤 1 给定起点1 的P标号：P[1]=0，其他节点标上T标号：
所有的T标号都改变为P标号。即得到从始点O到其他 各点的最短路权，标号过程结束。
2020/8/2
邓建华
1． Dijkstra法（标号法）
(2)算法步骤
Step1 初始化：给起点1标上P标号P(1)=0，其余 各点均表标上T标号T1(j)=∞，j=2,3… , . n。即表 示从起点1到1的最短路权为0，到其他各点的最短路 权的上限临时定为∞。标号中括号内数字表示节点号， 下标表示第几步标号。经过第一步标号得到一个P标 号P(1)=0。
还可以将规划年OD交通量分布预测值分配到规划 交通网络上，以评价交通网络规划方案合理性。
2020/8/2
邓建华
二、交通阻抗
交通阻抗（或者称为路阻）在交通流分配中通过 路阻函数来描述，所谓路阻函数是指路段行驶时间与 路段交通负荷，交叉口延误与交叉口负荷之间的关系。 在具体分配过程中，由路段行驶时间及交叉口延误共 同组成出行交通阻抗。
最短径路 一对OD点之间的径路中总阻抗最小的径路叫 “最短径路”。
2020/8/2
邓建华
（二）最短径路算法
最短径路算法是交通流分配中最基本也最重要的算 法，几乎所有交通流分配方法都是以它作为一个基 本子过程反复调用。最短路算法问题包含两个子问 题：两点间最小阻抗的计算和两点间最小阻抗径路 的辨识。在各类文献中，有关交通流分配最短径路 的算法很多，如Dijkstra法、矩阵迭代法、FloydWarshall法等。
2020/8/2
邓建华
二、交通阻抗
交通阻抗由两部分组成：路段阻抗和节点阻抗。
1.路段阻抗
城市道路：Ca f({V})
公路： Ca f (Va)
BPR公路行驶时间函数：
2020/8/2
ta
t0[1
qa ca
]
邓建华
2.节点阻抗
公路：因为路段比较长，路段延误占绝大 多数，一般不计交叉口延误。
第八章 交通流分配
本章内容
▪ 第一节 ▪ 第二节 ▪ 第三节 ▪ 第四节 ▪ 第五节 ▪ 第六节
概述 交通流分配中的基本概念 非平衡分配方法 平衡分配方法 随机分配方法 动态交通流分配
2020/8/2
邓建华
第一节 概述
明确几个问题：
？
•城市交通网络上形成的交通流量分布是两种机制相
互作用直至平衡的结果。
节点 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)
交通规划实际中，需要求出路网中任意两个节点之间 的最短路权矩阵（ n×n阶）；尽管Dijkstra算法一次能 够算出从起点到其他各节点的最短路权，但仍不能满足要 求，用此方法求最短路权矩阵，需要反复运算n次，导致 计算效率不高，且速度较慢，所需存储空间较多，在大规 模交通规划中应用受到一定限制。