第4节用户均衡问题的解法 1. Dijkstra法(记号确定法) 该方法是从离起点最近的点开始,逐渐向全方位枚举 出最短径路的方法。 【记号】 K:最短径路和最小费用已经确定的节点集合。 k:最短径路尚未确定的局部最小费用节点集合 最短径路的途径节点集 j:以o为起点的最小费用
第 4 节 用户均衡问题的解法 1． Dijkstra 法（记号确定法） 该方法是从离起点最近的点开始，逐渐向全方位枚举 出最短径路的方法。 【记号】 K :最短径路和最小费用已经确定的节点集合。 − K ：最短径路尚未确定的局部最小费用节点集合。 Fm ：最短径路的途径节点集合。 j c ：以 o 为起点的最小费用
【计算步骤】 Step1设所有节点的局部最小费用为c=或为足够 大的值,并设F=0,∈K 设o为起点,对节点o有∽=0,j=0,将节点o移 到集合K Step2检查以节点为起点的所有路段的终点四m},若满 足Cn >c.+ 则令Cm=C1+dm,F
【计算步骤】 Step 1 设所有节点j 的局部最小费用为c j = 或为足够 大的值，并设 − Fj = 0, j K 。 设 o 为起点，对节点 o 有co = 0, j = o ，将节点 o 移 到集合K 。 Step 2 检查以节点 i 为起点的所有路段的终点m ，若满 足 m i d m c c + ，则令c c d F i m = i + m , m =
Step3对最小费用尚未确定的节点集合k中的所有节 点,按下式计算局部最小费用的最小值C。 c=min(cn),{p:P∈K 将节点/移到集合K Step4如果cp=∞以外的节点是否全部被移到集合K 中,则结束计算。反之,令i=j,返回Step2 【最短径路的枚举】 利用F枚举出任意节点到起点o的最短径路 j→(F=→(F=)→(F8=)→…→(F=)起点o
Step 3 对最小费用尚未确定的节点集合 − K 中的所有节 点，按下式计算局部最小费用的最小值 j c 。 = − c c p p p K p j min( ), : 。 将节点 j 移到集合K 。 Step 4 如 果c p = 以外的节点是否全部被移到集合K 中，则结束计算。反之，令i = j ，返回 Step 2。 【最短径路的枚举】 利用Fj 枚举出任意节点 j 到起点 o 的最短径路： ( =) ( =) ( =) ( =) j h g Fb j F h F g F f 起点 o
【例题】用 Di jkstra法计算下图从点1到其它节点的最 短经路 节点及节点号码 路段及路段费用
【例题】用 Dijkstra 法计算下图从点 1 到其它节点的最 短经路。 1 56 4 7 23 2 2 2 1 1 1 1 3 3 4 4 6 8 9 节点及节点号码 路段及路段费用
解:将计算过程列于下图和表,可以看出,到第7步为 止,全部节点都被移到集合K中,结束计算。例如, 从节点1到节点6的最短径路为: 6→(F6=)7→(F7=4→(F4
解：将计算过程列于下图和表，可以看出，到第７步为 止，全部节点都被移到集合K 中，结束计算。例如， 从节点１到节点６的最短径路为： 6 (F6 =)7 (F7 =)4 (F4 =)1 1 56 4 7 23 2 2 2 1 1 1 1 3 3 4 4 6 8 9