最短路径分配法简介

最短路径分配法是指按所有出行者都选取出行最短的路线从出发点到目的地的原则分配交通量。“非平衡分配模型”的一种，是其他各种交通分配方法的基础。随着道路建设的发展，最短出行距离被最短交通阻抗取代，最常用的是出行时间。基本假定是车辆的行驶车速和交叉口延误都不受路段及交叉口交通量的影响，即每一路段长度(两交叉口之间的距离)上的出行时间均为常数。

其步骤为:①选定连通各对起讫点的最短路径。②将各对起讫点交通量分配到相应的最短路径上。③每个路段上每次被分配到的交通量的总和即为最后的分配交通量。由于交通量集中在最短路径上致使某些路径上的交通量可能为零，为此开发了容量限制分配法和多路径概率分配法，以求提髙对实际情况的模拟精度。又称“全有全无分配法”。

最短路径树Dijkstra算法

设置两个定点的集合T和S，集合S中存放已找到最短路径的定点，集合T中存放当前还未找到的最短路径的定点。初始状态时，集合S中只包含源点v0然后不断从集合T中选取到定点v0路径长度最短的顶点u加入集合S，集合S中每加入一个新的顶点u，都要修改定点v0到集合T中剩余顶点的最短路径长度值，集合T中每个顶点新的最短路径长度值为原来的最短路径长度值与定点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到集合S为止 。

最短路径树Floyd算法

从代表任意两个节点

考虑一个连通无向图

在一个所有最短路径都明确（例如没有负长度的环）的连通图，我们可以使用如下算法构造最短路径树：

使用Dijkstra算法或Floyd算法计算图 G 从根节点 v 到 顶点 u 的最短距离

对于所有的非根顶点

用各个顶点和它们的父节点之间的边构造最短最短路径树。

上面的算法保证了最短路径树的存在。像最小生成树一样，最短路径树通常也不只有一个的。在所有边的权重都相同的时候，最短路径树和广度优先搜索树一致。在存在负长度的环时，从

由图论的知识可知，地图上的点构成一带权无向图(有向图可视为特例的一种)，要找出任意两地间的最短路径,对地图中的所有点，首先要建立一个邻接矩阵，它表示图中任意两地间的邻接关系及其权值(若两地间无任何连接关系则设为无穷大)，易知该矩阵为对称矩阵。从该矩阵出发，可以利用图论中的迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法等求出最短路径。

Dijkstra算法

Dijkstra算法的基本思路是：首先，引进一个辅助向量Dist，它的每个分量Dist [i]表示当前找到的从始点V到每个终点Vi 的最短路径的长度。它的初始值为:若从V到Vi有弧，则Dist [i]为弧上的权值;否则置Dist[i]为无穷大。显然，长度为Dist[i]=Min{Dist[i]|Vi

Dijkstra算法描述为：

(1) 假设用带权的邻接矩阵Cost来表示带权有向图，Cost[i,j]表示弧(Vi , V j)上权值。若(Vi,Vj)不存在，则置Cost[i,j]为无穷大。S为已找到从V出发的最短路径的终点的集合，它的初始状态为空集。

(2) 选择Vj，使得Dist [i] =Min {Dist [i] |Vi 不

(4) 重复操作(2) , (3)共N-1次。由此求得从V到图上其余各顶点的最短路径是依路径长度递增的序列。

弗洛伊德算法

弗洛伊德算法能够求得每一对顶点之间的最短路径，其基本思想是：假设从顶点Vi到Vj的最短路径。若从Vi到Vj有弧，则从Vi到Vj存在一条长度为COST [ i, j]的路径，该路径不一定是最短路径，尚需进行n次试探。首先考虑路径(Vi, V1, Vj)是否存在(即判别弧(Vi, V1)和弧(V1, Vj)是否存在)。如果存在，则比较(Vi, Vj)和(Vi, V1, Vj)的路径长度，较短者为从Vi到Vj的中点顶点的序号不大于1的最短路径。假如在路径上再增加一个顶点V2，也就是说，若(Vi，…，V2)和(V2，...，Vj)分别是当前找到的中间顶点的序号不大于1的最短路径，那么(Vi，...，V2，...，Vj)就有可能是从Vi到Vj的中间顶点的序号不大于2的最短路径。将它和已经得到的从Vi 到Vj的中间顶点的序号不大于1的最短路径相比较，从中选出中间顶点的序号不大于2的最短路径之后，再增加一个顶点V3，继续进行试探。依次类推，在经过n次比较之后，最后求得的必是从Vi 到Vj的最短路径。按此方法，可同时求得各对顶点间的最短路径。算法共需3层循环，总的时间复杂度是O(