一、引言 现实生活中的许多经济现象通常都具有非常强的动态特征，人们对于这些现象一般是先进行数学上的抽象，然后用静态或统计的方法来加以研究和处理。从优化的理论和方法上看，经典的优化理论大多是站在旁观者的立场上看问题，即首先确定已知条件，然后在假设这些已知条件不变的基础上给出最优方案（即最优解）。条件一旦发生变化，这种方法所给出的最优方案就会失去其最优性。在变化的不确定因素对所考虑的问题影响很大的时候，经典的优化方法有：一是将可变化的因素随机化，寻求平均意义上的最优方案，二是考虑可变化因素的最坏情形，寻求最坏情形达到最优的方案。这两种处理方法对变化因素的一个特例都可能给出离实际最优解相距甚远的解，这显然是难以满足实际的要求的。那么是否存在一种方法，它在变化因素的每一个特例中都能给出一个方案，使得这一方案所得到的解离最优方案给出的解总在一定的比例之内呢?近年来兴起的局内问题与竞争算法的研究结果在一定意义上给如上问题一个肯定的答案。其实本文所提出的逆向标号算法就是对应局内最短路问题的一个竞争算法，从本质上来说它是一种贪婪算法，在不知将来情况的条件下，求出当前状态下的最优解。[1] 本文所考虑问题的实际背景是一个物流配送公司对其运输车辆的调度。假设物流公司需要用货车把货物从初始点O(Origin)运送到目的点D(Destination)。从日常来看，物流公司完全可以通过将整个城市交通网络看成一个平面图来进行运算，找到一条从O到D的最短路径以减少运输费用和节省运输时间。现考虑如下一个问题：如果当运输车辆沿着最短路径行驶到最短路径上的一点A，发现前方路径上的B点由于车辆拥塞而不能通过，车辆必须改道行驶，而此时物流配送公司应如何应对来保证其花费最低。问题推展开去，如果不是单个堵塞点，而是一个堵塞点序列，那物流配送公司又将如何来设计其最短路算法来在最短的时间内求出已知条件发生变化后的最优路径，从而有效的调度其运输车。 本文首先建立了物流配送公司动态最短路的数学模型，相比较给出了求本文所提出的动态最短路问题的传统算法和作者提出的逆向标号算法，并分析了各自的算法复杂度。 二、数学模型 假设城市交通网络是一个平面图，记为G，各个交通路口对应于图G上的各个顶点，令G=(G,V)为一边加权无向图，其中V为顶点的集合，E为边的集合，｜G｜=n，对于一般平面图上的三点之间，一定满足三角不等式，即任意三角形的两边之和一定不小于另外一边。对于本文要讨论的城市交通网络来说，即，任意三个结点之间的距离一定满足三角不等式。我们用O来表示运输的起始点，D表示运输的目的点。SP表示在没有路口堵塞情况下的最短路径，W(SP)表示沿着最短路径所要花费的运输费用。 以下的讨论都是基于如下的基本假设： 第一，去掉堵塞点后图G仍是连通的。 第二，只有当运输车走到前一点后，才能发现后面的一点发生堵塞而不能通过。 三、算法分析 对于本文的上述问题，有两种算法一（传统算法）和二（逆向标号算法）可以满足要求，但两种算法在求动态最短路的过程中都将会用到Dijkstra算法[2]，通过对Dijkstra算法的分析我们知道，Dijkstra算法采用了两个集合这样的数据结构来安排图的顶点，集合S表示已经被标记点的集合，集合(G-S)表示未被标记点的集合，一个点的标号是这个点到源节点的最短距离，算法的主要思想是：从G-S集合中选取具有最小标号的点w，而后把w点放入S集合中。因为S集合就是已经被标记点的集合，然后再从G-S集合中将所有经过点w而与源节点相通的v点的路径值T[v]统统作调整（如果存在某个点v，它的路径值大于已经被标记的点w的路径值与点v到点w的距离之和，那么就对所有与点v相通的点的路径值进行调整）。重复此过程直至所有的点全部进入S集合。 从以上的分析我们可以看出，当进行完Dijkstra算法，所有的点都将会被标号。首先我们先给出本节将会用到的符号和定义。我们用
表示沿着最短路从O点到A点的距离，W(
)表示沿着最优路径
从A点到D点的距离。Wij表示从i点到j点边的权，T[v]表示的v点标号值。[3] （一）算法一 第一步，对于给定的平面图G，运用Dijkstra算法求出从起点O点到终点D点的最优路径SP。 第二步，到达A点后，如果下一个顶点B发生车辆拥塞不能通车，计算子图G-{B}。 第三步，在此运用Dijkstra算法求出此时从A点到D点的最优路径
。
