交通规划07-1分配.ppt

三、 Floyd-Warshall法 算法简练。设网络中交叉点数为m，总节点数为n，则算法的计算量为m×n2次判断和赋值运算。 只能找到两个节点之间的一条最短路径。 例：如图交通网络，节点1、 3、7、9为PA点，其余节点 为交叉点，求所有节点之间 最小阻抗矩阵和倒数第二个 节点矩阵。 第三节 最短路径的求法 ④ ① ② ③ ⑤ ⑥ ⑦ ⑧ ⑨ 3 2 3 2 3 4 3 3 3 2 4 5 j i 1 2 3 4 5 6 7 8 9 1 0 3 ∞ 3 ∞ ∞ ∞ ∞ ∞ 2 3 0 3 ∞ 2 ∞ ∞ ∞ ∞ 3 ∞ 3 0 ∞ ∞ 4 ∞ ∞ ∞ 4 ∞ ∞ ∞ 0 3 ∞ 3 ∞ ∞ 5 ∞ 2 ∞ 3 0 ∞ ∞ 3 ∞ 6 ∞ ∞ 4 ∞ 2 0 ∞ ∞ 5 7 ∞ ∞ ∞ 3 ∞ ∞ 0 4 ∞ 8 ∞ ∞ ∞ ∞ 3 ∞ 4 0 2 9 ∞ ∞ ∞ ∞ ∞ 5 ∞ 2 0 j i 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 阻抗矩阵C 倒数第二点矩阵V j i 1 2 3 4 5 6 7 8 9 1 0 3 6 3 5 10 6 8 10 2 3 0 3 5 2 7 8 5 7 3 6 3 0 8 5 4 11 8 9 4 8 5 8 0 3 12 3 6 8 5 5 2 5 3 0 9 6 3 5 6 7 4 4 5 2 0 8 5 5 7 6 8 11 3 6 11 0 4 6 8 8 5 8 6 3 7 4 0 2 9 10 7 9 9 5 5 6 2 0 j i 1 2 3 4 5 6 7 8 9 1 1 1 2 1 2 3 4 5 8 2 2 2 2 5 2 3 4 5 8 3 2 3 3 5 2 3 4 5 6 4 2 5 2 4 4 3 4 5 8 5 2 5 2 5 5 3 4 5 8 6 2 5 6 5 6 6 4 5 6 7 2 5 2 7 4 9 7 7 8 8 2 5 2 5 8 9 8 8 8 9 2 5 6 5 8 9 8 9 9 ④ ① ② ③ ⑤ ⑥ ⑦ ⑧ ⑨ 3 2 3 2 3 4 3 3 3 2 4 5 第三节 最短路径的求法 三种最短路径算法特点总结： Dijkstra法 矩阵迭代法 Floyd Warshall法 通过前两种方法得到最小阻抗矩阵，之后，还需要把每一个节点对之间具体的最短路径寻找出来，以进行交通分配。 采用追踪法：从每条最短路径的起点开始，根据起点到各节点的最短路权有哪些信誉好的足球投注网站最短路径上的各个节点，直至路径终点 第四节 非均衡分配方法 一、全有全无分配法 设路段阻抗为常数，即假定走行时间不受路段上流量的影响，一次将一个PA点对的出行分布量全部分配到它们之间的最短路径上，叫做“全有全无分配法”，亦称“最短路径分配法”或“0-1”分配法。 是最简单、最基本的路径选择和分配方法，在美国芝加哥城交通规划中，首次获得应用；是其他分配方法的基础。 以例题说明全有全无分配法的算法。 ④ ① ② ③ ⑤ ⑥ ⑦ ⑧ ⑨ 3 2 3 2 3 4 3 3 3 2 4 5 A P 1 3 7 9 1 0 20 20 50 3 25 0 40 10 7 40 30 0 10 9 30 40 25 0 A P 1 3 7 9 1 1-2-3 1-4-7 1-2-5-8-9 3 3-2-1 3-2-5-4-7 3-6-9 7 7-4-5-2-1 7-4-5-2-3 7-8-9 9 9-8-5-2-1 9-6-3 9-8-7 给出交通网络各路段上的流量 ⑦ ⑧ ⑨ 70 40 60 70 50 30 40 10 70 50 ① ② ③ 10 60