主权项 |
1、一种公路网络最短路的计算方法,以标明相邻两地之间距离的地图为依据,并采用下述的计算方法编成计算机程进行计算:设M为一公路网络,V(M)为M中所有地点的集合,d(u,v)为地点u到地点v的公路长度,d(v)为起点x到地点v所走的某一条线路的长度,N(v)为与地点v相邻的公路网络M中已有的地点的集合。(a)令Max为公路网络M中所有道路长度的总和;Min为公路网络M中最短道路的长度;d(x)=0,S=V(M)-{x},x为起点,{x}为只包含起点x的集合;d(v)=d(x,v),v∈N(x);d(v)=Max,v∈S-N(x);Y=N(x);进入(b);(b)令ORD=Min+min{d(u)|u∈Y},min{d(u)|u∈Y}为在集合{d(u)|u∈Y}中求一个最小值;求Y的一个子集X,使X={v|d(v)<ORD};如果止点y∈X,则算法终止,否则S=S-X,Y=Y-X,进入(c);(c)对于X中的每一个地点v,依次进入(d);完毕之后返回到(b);(d)对于所有地点u,u∈N(v)∩S,使d(u)=min{d(u),d(v)+d(u,v)},min{d(u),d(v)+d(u,v)}为在d(u)和d(v)+d(u,v)中取最小的一个;Y=Y∪{u};完毕之后返回到(c)。 |