基于禁止路线网络的最短路问题研究

基于禁止路线网络的最短路问题研究

0禁止路线网络中的最短路问题算法在城市交通网络中，通常需要找到从起点到终点之间最短的交通路线。例如，出租车司机需要选择最短的路线来把客人送到目的地。这个问题很容易与图论中的正费用网络最短的问题一起，但理论与实践之间存在一定的差异。在图论中，如果在两点之间有一个连接的路径，则假定从其中点通过路径可以到达另一个点，但在现实的城市交通网络中并不总是这样。为了确保交通顺畅，交通管理部门经常制定了许多交通规则。例如，一些交叉口不能左转，一些交叉口不能直行，一些路段不能在某些路段禁止巡逻。这样，如果道路是相连的，就无法阻止它。作者提供了带有禁言网络的最短问题算法。该算法的基本思想是将有禁言网络转变为无禁言网络，然后使用无限制字段网络中的最短算法进行求解。1有向网络有向网络有向特点按禁止路线包含的有向弧的条数来分,禁止路线主要有两种情形:第一种情形,禁止路线仅包含一条有向弧,例如,在图1中,V1V5是一条禁止路线,此时,只要在图中删去有向弧V1V5,或在距离矩阵中将有向弧V1V5的长度定义为无穷大,直接用Dijkstra算法即可求得图中任意两点的最短距离;第二种情形,禁止路线包含两条有向弧,例如,在图1中,V1V5V4是一条禁止路线(相当于“禁止左转”情况),此时,就不能简单地在图中删去有向弧V1V5或V5V4了,因为如果这样,路线V1V5V3,或V2V5V4也变成禁止路线了,这显然是错误的.在现实生活的交通网络中,包含三条或三条以上的有向弧的禁止路线很少出现,例如在某个路口禁止左转,一般只与当前所在路段和下一路段有关,无需区分是从哪一路段到达当前路段的.因此本文考虑的禁止路线是专指第二种情形而言的,下面给出含有这种禁止路线的有向网络的数学描述.定义1含有禁止路线的有向网络是一个四元组N=(V,A,B,D),其中V是节点集,V={V1,V2,…,Vn},A是弧集,A={a1,a2,…,am},A中每一个元素ak是V中某两个元素Vi,Vj的有序对,记为ak=ViVj,称Vi为弧ak的头,Vj为弧ak的尾,k=1,…,m.对于弧ai=Vi1Vi2,aj=Vj1Vj2∈A,如果ai的尾等于aj的头,即Vi2=Vj1,则称aj是ai的直接后继.B是禁止路线集,B={b1,b2,…,bl},B中每一个元素br是V中某三个元素Vi,Vj,Vk的有序集,记为br=ViVjVk,其中ViVj,VjVk∈A,表示从节点Vi经有向弧ViVj到达节点Vj再经有向弧VjVk到达节点Vk的路线是禁止的,称ViVjVk是一条禁止路线.D是距离矩阵,D=(dij)n×n,dij≥0,dij={ViVj的弧长‚当ViVj∈A∞‚当ViVj∉A.0‚当i=j时定义2对于节点s,t∈V,以s为起点,t为终点的且不含禁止路线的有向路称为合法的s-t有向路,其所经过的所有有向弧的弧长之和称为该有向路的长度,所有合法的s-t有向路中长度最小的路称为s-t最短路.2节点s到节点t的最短路树算法首先考虑不含禁止路线的正费用网络G=(V,A,D)的最短路问题,所谓正费用网络,就是弧上的所有权为正数.Dijkstra于1959年提出一种求网络中一点到其余各点的最短路树算法,算法基本思想是:对于V中的每一个节点j,赋予两个数值(通常称为“标号”):一个是距离标号u(j),记录的是从起点到该节点的最短路长度的上界;另一个是前趋标号p(j),记录的是当起点s到该节点j的一条路长取到该上界u(j)时,该条路中节点j前面的那个直接前趋节点.算法不断修改这些标号,进行迭代计算.当算法结束时,距离标号表示的是从起点到该节点的最短路长度.最短路径可通过前趋标号反向追踪获得.将该最短路树算法稍作修改,便可得到从节点s到节点t的最短路算法,算法的具体步骤如下:STEP0(初始化)令S=Φ,ˉS=V,u(s)=0,p(s)=s;对V中节点j(j≠s),令初始距离标号u(j)=dsj,p(j)=s;STEP1如果t∈S,则u(t)为节点s到节点t的最短路长,最短路径可以通过前趋标号所记录的信息反向追踪获得,结束.否则,继续STEP2.STEP2从ˉS中找到距离标号最小的节点i,把它从ˉS删除,加入S.对于所有从i出发的弧ij∈A,若u(j)>u(i)+dij,则令u(j)=u(i)+dij,p(j)=i.转STEP1.3禁止路线网络n定义3给定含有禁止路线网络N=(V,A,B,D),按下述方式确定有向网络N′=(V′,A′,D′),以原网络N=(V,A,B,D)中的弧集A为转换网络N′=(V′,A′,D′)的节点集,即V′=A.按下述规则确定弧集A′以及距离矩阵D′=(d′ij)m×m:对于节点ai=Vi1Vi2∈V′,aj=Vj1Vj2∈V′,如果aj是ai的直接后继,即Vi2=Vj1,且Vi1Vi2Vj2∉B,则aiaj∈A′,d′ij=di1i2,否则aiaj∉A′,d′ij=∞,i,j=1,…,m.称网络N′=(V′,A′,D′)为网络N=(V,A,B,D)的转换网络.下面给出在含有禁止路线网络N=(V,A,B,D)中,以Vs为起点,Vt为终点的合法最短路算法:STEP0在网络N中,添加两个虚拟节点V0,Vn+1,以及两条虚拟有向弧V0Vs,VtVn+1,令d0j={0‚j=s或j=0‚∞‚其它di,n+1={0‚i=t或i=n+1‚∞‚其它将添加了虚拟节点和虚拟有向弧的网络记为N1;STEP1生成N1的转换网络Nnew;STEP2Nnew中用Dijkstra算法求出从起点V0Vs到终点VtVn+1的最短路.定理1按上述算法得到的Nnew网络中从起点V0Vs到终点VtVn+1的最短路径(Nnew中的一个节点序列,也是N中的一个有向弧序列),在去掉头尾的虚拟有向弧V0Vs和VtVn+1后,即是含有禁止路线网络N=(V,A,B,D)中从起点Vs到终点Vt的合法最短路(用有向弧序列表示).证明按照Nnew的构造,显然Nnew中任意一条从起点V0Vs到终点VtVn+1的路径,在去掉头尾的虚拟有向弧V0Vs和VtVn+1后(路径长度不变),即是N=(V,A,B,D)中从起点Vs到终点Vt的合法路径(用有向弧序列表示).另一方面,N中从起点Vs到终点Vt的一条合法路径(用有向弧序列表示),在始端添加虚拟有向弧V0Vs,在终端添加虚拟有向弧VtVn+1后(路径长度不变),必是Nnew中从起点V0Vs到终点VtVn+1的一条连通的有向路.于是Nnew中从起点V0Vs到终点VtVn+1的最短路径,在去掉头尾的虚拟有向弧V0Vs和VtVn+1后,必是N中从起点Vs到终点Vt的合法的最短路(用有向弧序列表示).4最短路径及其转换网络如图1,有向弧边上的数字表示有向弧长度,V1V5V4是一条禁止路线,求从V1到V4的最短路线.STEP0:给图1添加虚拟节点和虚拟有向弧,得图2.STEP1:再生成图2的转换网络,得图3.STEP2:在图3中,以e0为起点,e9为终点,由Dijkstra算法计算最短路.为节省篇幅,将迭代过