,708 北京科技大学学报 第30卷 疑是一个制约算法速度的瓶颈，当Dijkstra算法求 ④计算最短路径h=d(vm)十e(vn),l2= 解最短路径的过程中，通常执行了许多与此无关的 d(vx)十e(v,)十l(vx,v,),式中l(vx,v,)表示vx、 顶点的最短路径，增加了额外的运算量，从而降低了 v,相邻两点的路权值.l(vx,vy)>0;vx∈P;v,∈ 算法的效率，因此，不需要计算从救灾地点到所有 Q.最短路径为lmim=min{lh,l2}. 地点的最短路径，只需计算从救灾地点到受灾地点 (3)井下情况复杂，火灾灾变时期，巷道通行状 之间的最短路径，将受灾地点是否进入集合S作为 况是不断变化的，选择出的最佳救灾路线也要随着 运算停止判断的条件，可减少Dijkstra算法的标记 巷道状况的变化而变化，因此，在设计程序时应充 步数 分考虑到巷道灾变时的特点，选出的救灾路线随着 (2)考虑将最短路径问题分解为多个子问题进 巷道条件的变化而改变.例如，三水平轨道巷发生 行求解。这样可以降低问题复杂度，符合并行处理 火灾时，救灾人员需从主井出发到达受灾地点，在搜 思想，Dikstra最短路径算法是从起点到终点求最短 索救灾路线之前，可用鼠标选择想要查看的巷道， 路径，同样也可以表述为从终点到起点求最短路径， 如选择一480北翼运输大巷，此时弹出显示巷道属性 于是考虑最短路径问题可以分解为由起点到终点求 的界面（见图1），点击“灾变时期各参数输入”按钮， 解最短路径和由终点到起，点求解最短路径两个子问 可查看并更改一480北翼运输大巷灾变时期的情况 题.算法步骤为： (见图2)，图2(a)中高温烟流的温度为20℃， ①开始时，P=0,Q=0,vm=v1,vn=vN 图2(b)中高温烟流的温度为58℃.当高温烟流的 P、Q分别是由开始点1、终点N开始的扩展点 温度为20℃时，救灾人员可从一480北翼运输大巷 (固定标号)集合，vm、vm分别是集合P、Q的当前 通过，搜索出的最佳救灾路线如图3(a)所示，当高 扩展点 温烟流的温度为58℃时，计算机根据一480北翼运 ②d(m)=m吧d(:),e(w）= 输大巷首末节点的标高，判断出救灾人员上行或者 m(,),其中d(um)和e(vn)分别为起点到 下行，若判断结果为水平行进或者下行，根据式(2) vm、终点到vm的最短路径，PU{vm}→P,OU 判断此巷道是否可通行；若判断结果为上行，则根据 式(3)判断此巷道是否可通行.经计算，58℃时480 n0 北翼运输大巷不可通行，搜索出的最佳救灾路线如 ③重复②直到P∩Q={m)且vm唯一时 图3（凸）所示. 终止 天安时梨各参影推入 图1一180北翼运输大巷属性 Fig.1 Attribute of-480 north wing transportation roadway疑是一个制约算法速度的瓶颈．当 Dijkstra 算法求 解最短路径的过程中‚通常执行了许多与此无关的 顶点的最短路径‚增加了额外的运算量‚从而降低了 算法的效率．因此‚不需要计算从救灾地点到所有 地点的最短路径‚只需计算从救灾地点到受灾地点 之间的最短路径‚将受灾地点是否进入集合 S 作为 运算停止判断的条件‚可减少 Dijkstra 算法的标记 步数． （2） 考虑将最短路径问题分解为多个子问题进 行求解．这样可以降低问题复杂度‚符合并行处理 思想．Djkstra 最短路径算法是从起点到终点求最短 路径‚同样也可以表述为从终点到起点求最短路径． 于是考虑最短路径问题可以分解为由起点到终点求 解最短路径和由终点到起点求解最短路径两个子问 题．算法步骤为： ① 开始时‚P＝∅‚Q＝∅‚v m＝ v1‚v n＝ v N． P、Q 分别是由开始点 v1、终点 v N 开始的扩展点 （固定标号）集合‚v m、v n 分别是集合 P、Q 的当前 扩展点． ② d （ v m ） ＝ min v x∈P ｛d （ v x ）｝‚e （ v n ） ＝ min v y∈ Q ｛e（ v y）｝‚其中 d （ v m ）和 e（ v n ）分别为起点到 v m、终点到 v n 的最短路径‚P ∪｛v m｝→ P‚Q ∪ ｛v n｝→ Q． ③ 重复②直到 P∩ Q ＝｛v m ）且 v m 唯一时 终止． ④ 计算最短路径 l1＝ d （ v m ）＋ e （ v n ）‚l2＝ d（ v x）＋e（ v y）＋ l（ v x‚v y）‚式中 l（ v x‚v y）表示 v x、 v y 相邻两点的路权值．l（ v x‚v y）＞0；v x∈ P；v y∈ Q．最短路径为 lmin＝min｛l1‚l2｝． （3） 井下情况复杂‚火灾灾变时期‚巷道通行状 况是不断变化的‚选择出的最佳救灾路线也要随着 巷道状况的变化而变化．因此‚在设计程序时应充 分考虑到巷道灾变时的特点‚选出的救灾路线随着 巷道条件的变化而改变．例如‚三水平轨道巷发生 火灾时‚救灾人员需从主井出发到达受灾地点‚在搜 索救灾路线之前‚可用鼠标选择想要查看的巷道． 如选择—480北翼运输大巷‚此时弹出显示巷道属性 的界面（见图1）‚点击“灾变时期各参数输入”按钮‚ 可查看并更改—480北翼运输大巷灾变时期的情况 （见图2）．图2（a） 中高温烟流的温度为20℃‚ 图2（b）中高温烟流的温度为58℃．当高温烟流的 温度为20℃时‚救灾人员可从—480北翼运输大巷 通过‚搜索出的最佳救灾路线如图3（a）所示．当高 温烟流的温度为58℃时‚计算机根据—480北翼运 输大巷首末节点的标高‚判断出救灾人员上行或者 下行．若判断结果为水平行进或者下行‚根据式（2） 判断此巷道是否可通行；若判断结果为上行‚则根据 式（3）判断此巷道是否可通行．经计算‚58℃时—480 北翼运输大巷不可通行‚搜索出的最佳救灾路线如 图3（b）所示． 图1 —480北翼运输大巷属性 Fig．1 Attribute of —480north wing transportation roadway ·708· 北 京 科 技 大 学 学 报 第30卷