最短路徑算法在礦山巷道三維模型網(wǎng)絡(luò)分析中的應(yīng)用

車德福 陳軍偉 趙西亭

(東北大學(xué)資源與土木工程學(xué)院,遼寧 沈陽 110819)

最短路徑算法在礦山巷道三維模型網(wǎng)絡(luò)分析中的應(yīng)用

車德福 陳軍偉 趙西亭

(東北大學(xué)資源與土木工程學(xué)院,遼寧 沈陽 110819)

礦山巷道三維模型能真實(shí)地模擬井下的工作場(chǎng)景，基于該模型的網(wǎng)絡(luò)分析對(duì)煤礦井下安全救援十分重要。根據(jù)巷道的網(wǎng)絡(luò)特點(diǎn)，將實(shí)際的測(cè)量數(shù)據(jù)中點(diǎn)狀和線狀元素抽象為節(jié)點(diǎn)-弧段圖，該圖的生成對(duì)應(yīng)著一維中心線和二維雙線巷道的構(gòu)建，在此基礎(chǔ)上根據(jù)斷面的拱高、墻高及拓?fù)潢P(guān)系進(jìn)行井巷模型基本單元自動(dòng)的裝配以及三角化生成巷道的三維模型。網(wǎng)絡(luò)分析采用能適應(yīng)拓?fù)渥兓腄ijkstra算法，從減少搜索節(jié)點(diǎn)和采用鄰接表的存儲(chǔ)結(jié)構(gòu)兩方面對(duì)傳統(tǒng)的Dijkstra算法進(jìn)行優(yōu)化，并分析了算法的效率。最后編寫程序?qū)崿F(xiàn)了改進(jìn)后算法在巷道三維模型中存在障礙的情況下的最短路徑分析，并能在三維巷道中漫游顯示，結(jié)果表明該算法快捷有效。

最短路徑算法 Dijkstra 三維模型 巷道網(wǎng)絡(luò) 漫游

巷道是礦山中最重要的空間要素，具有三維網(wǎng)絡(luò)特征。通過計(jì)算機(jī)技術(shù)對(duì)礦山巷道的基礎(chǔ)數(shù)據(jù)進(jìn)行管理實(shí)現(xiàn)礦山巷道的三維模型的構(gòu)建，能真實(shí)地模擬井下的工作場(chǎng)景，提高礦山的管理水平及工作效率。國內(nèi)外大量學(xué)者對(duì)礦山巷道的交互建模問題開展了研究，國外已有多家公司推出了商業(yè)化三維數(shù)字礦山建模軟件(如Lynx，Surpac，GOCAD，Micromine，CTech，EarthVision等)，上述軟件的3D功能大多集中在3D建模的可視化方面，空間分析功能則顯得不足[1]。網(wǎng)絡(luò)分析是空間分析的一個(gè)重要方面，最短路徑分析在網(wǎng)絡(luò)分析中占據(jù)著主導(dǎo)地位，因此深入地研究最短路徑算法在礦山三維巷道網(wǎng)絡(luò)分析中的應(yīng)用就顯得十分必要。

本研究從巷道具有網(wǎng)絡(luò)的特點(diǎn)出發(fā)，首先對(duì)巷道數(shù)據(jù)進(jìn)行了組織，給出了構(gòu)建巷道三維模型的方法，基于優(yōu)化的Dijkstra算法在構(gòu)建的模型中進(jìn)行最短路徑分析，最后在三維巷道模型中漫游顯示，對(duì)礦山安全問題中的避災(zāi)救險(xiǎn)有一定的幫助。

1 礦山三維巷道網(wǎng)絡(luò)數(shù)據(jù)的組織

礦山巷道一般是根據(jù)開采水平(簡稱水平，指地下采煤時(shí)，將井田沿傾斜方向按一定高度劃分的開采范圍)、采區(qū)(在階段范圍內(nèi)，沿走向把階段劃分為具有獨(dú)立生產(chǎn)系統(tǒng)的塊)、工作面(直接進(jìn)行采掘或排碴的場(chǎng)所)、工作地點(diǎn)(巷道名稱)區(qū)分的。巷道網(wǎng)絡(luò)空間數(shù)據(jù)具有以下特點(diǎn)[2]：①整個(gè)巷道網(wǎng)絡(luò)可以按照開采水平來劃分，例如-450 m水平、-600 m水平等，不同開采水平通過井筒聯(lián)系；②某一開采水平的巷道網(wǎng)絡(luò)除了井底車場(chǎng)附近處較為稠密外，其他地方一般都比較稀疏，如運(yùn)輸大巷、采區(qū)上下山等；③巷道網(wǎng)絡(luò)中存在有很多硐室，硐室就是為某種專門用途在井下開鑿和建造的斷面較大或長度較短的空間構(gòu)筑物。

要對(duì)巷道網(wǎng)絡(luò)進(jìn)行路徑分析，就需要構(gòu)建巷道網(wǎng)絡(luò)數(shù)據(jù)間的拓?fù)潢P(guān)系，本研究從圖的角度出發(fā)，將現(xiàn)實(shí)世界中的巷道地理網(wǎng)格抽象成節(jié)點(diǎn)-弧段圖，然后基于圖來解決巷道網(wǎng)絡(luò)分析問題。

根據(jù)以下原則把巷道測(cè)量數(shù)據(jù)轉(zhuǎn)換成節(jié)點(diǎn)-弧段圖的節(jié)點(diǎn)：①所有巷道交叉處應(yīng)設(shè)置成節(jié)點(diǎn)；②考慮到轉(zhuǎn)彎限制對(duì)權(quán)值的影響，巷道轉(zhuǎn)彎處也應(yīng)設(shè)置成節(jié)點(diǎn)；③所有的設(shè)施處應(yīng)設(shè)置成節(jié)點(diǎn)，如水倉、泵房、風(fēng)機(jī)房、變電所、主副井、儲(chǔ)藏室、硐室等；④考慮到巷道三維模型的構(gòu)建都使用測(cè)量成果，所有測(cè)量點(diǎn)也作為節(jié)點(diǎn)。

弧段對(duì)應(yīng)著巷道網(wǎng)絡(luò)中的線狀元素，可以把運(yùn)輸大巷、切眼等巷道的中心線抽象為弧段。在最短路徑救援時(shí)用巷道的長度表示弧段的權(quán)值。根據(jù)以上原則轉(zhuǎn)化的結(jié)果如圖1所示。

圖1 巷道中心線節(jié)點(diǎn)-弧段圖

2 礦山巷道三維模型的構(gòu)建及漫游顯示

巷道三維模型的構(gòu)建主要包括一維中心線建模，二維雙線巷道建模，三維井巷工程建模等步驟[3]。

一維中心線建模：井巷工程中心數(shù)據(jù)由導(dǎo)線生成，通過交叉點(diǎn)數(shù)據(jù)的檢測(cè)與計(jì)算、彎道數(shù)據(jù)的離散擬合與中心線拓?fù)潢P(guān)系建立等，生成具有拓?fù)潢P(guān)系的井巷工程中心線網(wǎng)絡(luò)(網(wǎng)絡(luò)上的每一條線段即是一段巷道)，這個(gè)網(wǎng)絡(luò)是巷道空間分析、巷道漫游等功能實(shí)現(xiàn)的基礎(chǔ)。

二維雙線巷道建模：就是建立通常圖紙資料上的二維井巷工程雙線輪廓，基于已經(jīng)建立的一維中心線網(wǎng)絡(luò)模型，根據(jù)每一段巷道的寬度、方位角以及其他參數(shù)，計(jì)算雙線巷道邊線交點(diǎn)的坐標(biāo)，從而構(gòu)建二維雙線巷道。

三維井巷工程建模：根據(jù)生成的雙線巷道、每一斷面的拱高、墻高及其拓?fù)潢P(guān)系，按一定的規(guī)則進(jìn)行井巷模型基本單元自動(dòng)的裝配，進(jìn)行必要的三角化，進(jìn)而生成井巷工程的三維模型。

虛擬漫游技術(shù)是基于地理信息技術(shù)、虛擬現(xiàn)實(shí)技術(shù)、計(jì)算機(jī)技術(shù)等高新技術(shù)的一種應(yīng)用[4]。經(jīng)過一定的算法與智能化設(shè)計(jì)，建立與現(xiàn)實(shí)相一致的虛擬場(chǎng)景，用戶能在場(chǎng)景自由地瀏覽和查詢，有身臨其境的感覺。OpenGL 所具有的平移、縮放、旋轉(zhuǎn)等功能為實(shí)現(xiàn)三維場(chǎng)景的實(shí)時(shí)動(dòng)態(tài)漫游提供了保證，借助OpenGL，建立三維模型場(chǎng)景庫，建立虛擬三維場(chǎng)景空間，實(shí)現(xiàn)的過程主要包括漫游路徑的設(shè)計(jì)、漫游控制、碰撞檢測(cè)以及模型簡化等關(guān)鍵技術(shù)[3]。

3 最短路徑算法

最短路徑算法中Dijkstra 算法由于能適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓?，性能穩(wěn)定 ，因而在計(jì)算機(jī)網(wǎng)絡(luò)拓?fù)渎窂竭x擇以及GIS中得到廣泛的應(yīng)用。傳統(tǒng)的Dijkstra算法[5]用于尋求從一個(gè)固定起點(diǎn)到其余各點(diǎn)的最短路徑，是典型的單源最短路徑算法，主要特點(diǎn)是以起始點(diǎn)為中心向外層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。

Dijkstra算法的基本思路[5-6]是：按路徑長度遞增的順序，逐個(gè)產(chǎn)生各節(jié)點(diǎn)j最短路徑。設(shè)G=(V,E)是一個(gè)賦權(quán)圖，把圖中頂點(diǎn)集合V分成2組，第1組為已求出最短路徑的頂點(diǎn)集合(用S表示，初始時(shí)S中只有1個(gè)源點(diǎn)，以后每求得1條最短路徑，就將加入到集合S中，直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了)；第2組為其余未確定最短路徑的頂點(diǎn)集合(用U表示)，按最短路徑長度的遞增次序依次把第2組的頂點(diǎn)加入S中。在加入的過程中，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)1個(gè)距離，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長度，U中的頂點(diǎn)的距離是從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長度。傳統(tǒng)Dijkstra算法比較簡單，容易實(shí)現(xiàn)，理論上，用該算法解決最短路徑問題已經(jīng)很成熟。

3.1 Dijkstra 算法的優(yōu)化

礦山事故發(fā)生時(shí)，為保證最快速度搜索到最優(yōu)避災(zāi)路徑，采取基于Dijkstra算法的改進(jìn)算法來進(jìn)行路徑搜索。針對(duì)礦山巷道的網(wǎng)絡(luò)空間分布特點(diǎn)，考慮到傳統(tǒng)算法以鄰接矩陣方式存儲(chǔ)數(shù)據(jù)，造成大量空間的浪費(fèi)，而且難以全面地描述真實(shí)的巷道網(wǎng)絡(luò)信息，如節(jié)點(diǎn)的屬性信息及弧的屬性信息等。對(duì)Dijkstra算法從時(shí)間和存儲(chǔ)空間2個(gè)方面進(jìn)行改進(jìn)。

(1)時(shí)間上：根據(jù)縮小搜索區(qū)域的思想[7-8]，根據(jù)巷道的點(diǎn)—弧段圖的實(shí)際場(chǎng)景，通過減少搜索的節(jié)點(diǎn)數(shù)目實(shí)現(xiàn)。

(2)存儲(chǔ)空間上：巷道網(wǎng)絡(luò)為大型稀疏網(wǎng)絡(luò)，考慮采用鄰接鏈表的方式來描述巷道網(wǎng)絡(luò)的連通關(guān)系及屬性信息。

3.1.1 Dijkstra 算法時(shí)間方面的優(yōu)化

巷道數(shù)據(jù)抽象成的節(jié)點(diǎn)-弧段圖有很多不必要的節(jié)點(diǎn)，因此可以通過對(duì)巷道網(wǎng)絡(luò)圖簡化來減少算法的搜索時(shí)間。

巷道網(wǎng)絡(luò)中存在很多硐室，如圖1中E1-E2為例，在路徑分析中，節(jié)點(diǎn)E2的弧段連接數(shù)為1，如果節(jié)點(diǎn)E2既不是起始節(jié)點(diǎn)，又不是終止節(jié)點(diǎn)外，路徑分析中肯定不會(huì)經(jīng)過節(jié)點(diǎn)E2，所以可以將節(jié)點(diǎn)E2和節(jié)點(diǎn)E1的鄰接邊E1-E2去除。然后，對(duì)路徑初始化，將與起始節(jié)點(diǎn)S有鄰接關(guān)系的所有弧段，加入到路徑鏈表中，并且對(duì)其做標(biāo)記，表示已經(jīng)對(duì)該弧段搜索。接著進(jìn)行路徑搜索，分別對(duì)與路徑鏈表中節(jié)點(diǎn)(與前一個(gè)節(jié)點(diǎn)對(duì)應(yīng))有鄰接關(guān)系的弧段搜索，并對(duì)其做標(biāo)記，如果該弧段的另一節(jié)點(diǎn)已經(jīng)在路徑中存在，比較該節(jié)點(diǎn)路徑權(quán)值大小，將較小節(jié)點(diǎn)加入路徑。直至搜索到終止點(diǎn)。最后，選擇起始節(jié)點(diǎn)與終止節(jié)點(diǎn)間的最短路徑。從終止節(jié)點(diǎn)開始搜索其前一個(gè)節(jié)點(diǎn)，搜到起止節(jié)點(diǎn)為止。

3.1.2 Dijkstra算法存儲(chǔ)空間方面的優(yōu)化

礦山巷道網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)復(fù)雜，數(shù)據(jù)量大,設(shè)圖有n個(gè)節(jié)點(diǎn)，用傳統(tǒng)鄰接矩陣存儲(chǔ)結(jié)構(gòu)，其空間復(fù)雜度為 。礦山巷道網(wǎng)絡(luò)抽象的節(jié)點(diǎn)-弧段圖屬于稀疏圖(每個(gè)巷道交叉口所連接的巷道一般為2～5個(gè)，巷道的數(shù)目遠(yuǎn)遠(yuǎn)小于 )。適宜采用鄰接表存儲(chǔ)結(jié)構(gòu)，它既能節(jié)省存儲(chǔ)空間也容易實(shí)現(xiàn)，且可根據(jù)需要擴(kuò)充數(shù)據(jù)域，有利于全面反映礦山巷道的網(wǎng)絡(luò)特征。

路徑存儲(chǔ)采用單向鏈表的數(shù)據(jù)結(jié)構(gòu)如表1所示。

表1 路徑的數(shù)據(jù)結(jié)構(gòu)

節(jié)點(diǎn)與弧段的鄰接表存儲(chǔ)結(jié)構(gòu)用C++語言描述為

class CNonGraVex

{

頂點(diǎn)坐標(biāo)以及標(biāo)識(shí)等屬性；

繪制特殊顯示等基本方法；

};

class CNonGraArc

{

弧尾標(biāo)識(shí)以及弧的權(quán)重；

BOOL mark;∥最短路徑路線標(biāo)識(shí)；

BOOL Arcmark;∥弧的標(biāo)記,是否有障礙；

相關(guān)的的操作；

};

3.2 Dijkstra算法改進(jìn)后效率分析

在實(shí)際的礦山巷道中，如果某一平巷內(nèi)出現(xiàn)瓦斯涌出量過高、坍塌、涌水、冒頂或火災(zāi)等危險(xiǎn)障礙，導(dǎo)致該平巷不能通行，就需要考慮如何避開這些事故路段到達(dá)目的地。把該因素考慮進(jìn)去后改進(jìn)的Dijkstra最短路徑分析搜索方法總結(jié)如下。

Step1：確定要搜索的起止節(jié)點(diǎn)，并對(duì)節(jié)點(diǎn)-弧段圖進(jìn)行簡化；

Step2：初始化起始節(jié)點(diǎn)的路徑，將路徑中的每一個(gè)弧段都定義成∞，不可通過；

Step3：對(duì)路徑節(jié)點(diǎn)逐步搜索、更新路徑，直至搜到終止節(jié)點(diǎn)，并將路徑中的各個(gè)節(jié)點(diǎn)都記錄下來，并記錄路徑的長度；

Step4：選擇出起止節(jié)點(diǎn)間的最短路徑，并將最短路徑用可區(qū)分的顏色顯示出來。

Step5：對(duì)于出現(xiàn)事故的路段進(jìn)行“添加障礙”的標(biāo)志，將事故路段定為不通，然后重復(fù)上述的4步重新搜索新路徑，將路徑更新。

算法效率分析[9-11]：假設(shè)初始節(jié)點(diǎn)-弧段圖有n個(gè)節(jié)點(diǎn)。第1步中對(duì)所有節(jié)點(diǎn)循環(huán)，其時(shí)間復(fù)雜度為O(n)。第2步中對(duì)所有節(jié)點(diǎn)循環(huán)，時(shí)間復(fù)雜度為O(n)。第3步中，第1次循環(huán)為與起始點(diǎn)相鄰的弧段的數(shù)目m，第2次循環(huán)次數(shù)為m-1加上與第1次找到的頂點(diǎn)直接相鄰的弧段的數(shù)目。以此類推，直到所有節(jié)點(diǎn)搜索完畢為止。最壞情況下，也就是這n個(gè)節(jié)點(diǎn)之間都有直接相鄰關(guān)系，那么每次循環(huán)次數(shù)為(n-1),(n-2),…,1，那么其時(shí)間復(fù)雜度是它們的和為O(n2)。第4步中，對(duì)所有保存路徑循環(huán)，最壞情況下為所有弧段個(gè)數(shù)T，其時(shí)間復(fù)雜度為O(n2)。因此改進(jìn)的Dijkstra最短路徑分析方法的時(shí)間復(fù)雜度為max{O(n),O(n2),O(n)}，即為O(n2)。這與Dijkstra最短路徑分析方法的時(shí)間復(fù)雜度一致，但是注意到實(shí)際礦山網(wǎng)絡(luò)數(shù)據(jù)中，巷道弧段個(gè)數(shù)T?n2，所以此改進(jìn)算法可以有效地消除大量的冗余存儲(chǔ)和計(jì)算，很大程度上提高算法效率。

4 仿真實(shí)現(xiàn)

設(shè)計(jì)程序首先構(gòu)建三維模型，單擊屏幕選擇搜索的起點(diǎn)和終點(diǎn)，使用Dijkstra算法確定出最短路徑，并用綠色標(biāo)識(shí)出來。對(duì)于出現(xiàn)障礙的路徑，通過設(shè)置變量的值，重新建立拓?fù)潢P(guān)系，找出當(dāng)前的最短路徑，具體實(shí)現(xiàn)如下：

讀取巷道數(shù)據(jù)庫中的導(dǎo)線數(shù)據(jù)，根據(jù)節(jié)點(diǎn)之間的拓?fù)潢P(guān)系建立起節(jié)點(diǎn)-弧段圖，構(gòu)建巷道，巷道三維模型主要是由雙線巷道以及巷道三角面構(gòu)成，如圖2所示。

圖2 礦山巷道三維模型

在巷道模型中，根據(jù)實(shí)際巷道中避災(zāi)的需要選擇起點(diǎn)和終點(diǎn)，選擇菜單中的“巷道最短路徑搜索”，得出最短路徑并標(biāo)示出來，如圖3所示。

圖3 巷道最短路徑搜索

如果巷道中存在安全隱患或出現(xiàn)事故時(shí)，某條巷道可能會(huì)不通。當(dāng)前的路徑肯定要發(fā)生變化，將發(fā)生事故段用紅線標(biāo)出，表示此路不通，對(duì)應(yīng)地在程序中就是添加1個(gè)障礙，并將表示該弧段的標(biāo)記變量Arcmark更改為“TRUE”，清除當(dāng)前路徑，重新建立拓?fù)潢P(guān)系，得到有障礙的最短路徑，如圖4所示。

圖4 有障礙時(shí)的最短路徑

對(duì)于建立的最短路徑，可以在其中進(jìn)行漫游，清晰地查看最短路徑中各個(gè)巷道的連接以及避災(zāi)時(shí)的行走路徑，如圖5所示。

圖5 最短路徑巷道內(nèi)部漫游

5 結(jié) 語

從巷道具有網(wǎng)絡(luò)的特點(diǎn)出發(fā)，對(duì)傳統(tǒng)的Dijkstra算法進(jìn)行了改進(jìn)，能有效地減少節(jié)點(diǎn)搜索范圍和計(jì)算復(fù)雜度，將其應(yīng)用到礦山巷道網(wǎng)絡(luò)最短路徑的分析中，在礦山巷道三維模型中漫游顯示，能真實(shí)地再現(xiàn)巷道的場(chǎng)景，對(duì)礦山的安全救援有一定的幫助。最短路徑分析等網(wǎng)絡(luò)分析一般是在瓦斯監(jiān)測(cè)系統(tǒng)實(shí)時(shí)監(jiān)測(cè)、預(yù)警危險(xiǎn)，視頻監(jiān)控系統(tǒng)提供的當(dāng)前巷道的視頻信息，人員定位系統(tǒng)提供的人員實(shí)時(shí)位置信息的基礎(chǔ)上實(shí)施的，與這3大系統(tǒng)的集成能使礦山管理人員更方便地做出決策，提高管理水平，這也是今后工作的研究方向。

[1] 車德福，吳立新．?dāng)?shù)字礦山基礎(chǔ)平臺(tái)——GeoMo3D的功能結(jié)構(gòu)與應(yīng)用[C]∥第七屆全國礦山測(cè)量學(xué)術(shù)會(huì)議論文集．北京:中國煤炭學(xué)會(huì),2007：142-148． Che Defu，Wu Lixin.Functional structure and application of the basic Information platform of digital mine：GeoMo3D[C]∥The Proceedings of the Seventh National Academic Meeting on Mine Surveying.Beijing：China Coal Society,2007：142-148.

[2] 丁宜晨．井下工程交互設(shè)計(jì)系統(tǒng)研發(fā)及應(yīng)用[D]．沈陽：東北大學(xué)，2012． Ding Yichen.Research of Three-Dimensional Interactive Design Subsystem for Sinking and Drifting Engineering and Its Applications[D].Shenyang：Northeastern University，2012.

[3] 高光亮．基于煤礦井三維模型的漫游查詢模塊研究與實(shí)現(xiàn)[D]．沈陽：東北大學(xué)，2013． Gao Guangliang.Research and Implementation of Roam-query Module Based on Three-dimensional Coal Mine Models[D].Shenyang：Northeastern University，2013.

[4] 劉林濤.建筑場(chǎng)景虛擬漫游關(guān)鍵技術(shù)的研究和實(shí)現(xiàn)[D] ．蘇州：蘇州大學(xué)，2008. Liu Lintao.Research and Implement of Key Technology for Virtual Architecture Environment[D].Suzhou：Soochow University，2008.

[5] 張渭軍，王 華．城市道路最短路徑的Dijkstra算法優(yōu)化[J]．長安大學(xué)學(xué)報(bào)：自然科學(xué)版，2005，25(6)：62-65． Zhang Weijun，Wang Hua.Optimization dijkstra arithmetic for shortest path of urban traffic net[J].Journal of Chang'an University:Natural Science ，2005,25(6):62-65.

[6] 王戰(zhàn)紅，孫明明，姚 瑤．Dijkstra算法的分析與改進(jìn)[J]．湖北第二師范學(xué)院學(xué)報(bào)，2008，25(8)：12-14． Wang Zhanhong，Sun Mingming，Yao Yao.Analysis and improvement of dijkstra algorithm[J].Journal of Hubei University of Education，2008，25(8):12-14.

[7] 鄭四發(fā)，曹劍東，連小珉．復(fù)雜路網(wǎng)下多客戶間最短路徑的扇面Dijkstra算法[J]．清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，49(11):1834-1837. Zheng Sifa，Cao Jiandong，Lian Xiaomin.Sector dijkstra algorithm for shortest routes between customers in complex road networks[J].Journal of Tsinghua University：Science and Technology，2009，49(11):1834-1837.

[8] 董 俊，黃傳河．改進(jìn)Dijkstra算法在GIS導(dǎo)航應(yīng)用中最短路徑搜索研究[J]．計(jì)算機(jī)科學(xué)，2012，39(10):245-247. Dong Jun，Huang Chuanhe.Research on shortest path search of improved dijkstra algorithm in GIS navigation application[J].Computer Science，2012，39(10):245-247.

[9] 蔚 潔，楊懷雷，成汝震．基于Dijkstra算法的最優(yōu)路徑搜索方法[J]．河北師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，32(5)：590-598． Yu Jie，Yang Huailei，Cheng Ruzhen.The research and application of formal requirement analysis method based on evolved component[J].Hebei Normal University：Natural Science Edition，2008，32(5):590-598.

[10] 王兆南．基于Dijkstra算法改進(jìn)的海量數(shù)據(jù)最優(yōu)路徑計(jì)算方法研究與實(shí)現(xiàn)[J]．測(cè)繪通報(bào)，2012(9)：32-37． Wang Zhaonan.Mass data optimal path searching using an improved dijkstra algorithm[J].Bulletin of Surveying and Mapping，2012(9)：32-37.

[11] 姜鳳輝，李樹軍，姜鳳嬌，等．基于GIS的Dijkstra改進(jìn)算法及其在交通導(dǎo)航系統(tǒng)中的應(yīng)用[J]．測(cè)繪與空間地理信息，2011，34(4)：129-131． Jiang Fenghui，Li Shujun，Jiang Fengjiao，et al.The dijkstra algorithm improved a navigation system and its application in the traffic based on GIS[J].Geomatics & Spatial Information Technology.2011，34(4)：129-131.

(責(zé)任編輯 石海林)

Application of Shortest Route Algorithm in Network Analysis of 3D Tunnel Modeling

Che Defu Chen Junwei Zhao Xiting

(CollegeofResourcesandCivilEngineering，NortheasternUniversity，Shenyang100819，China)

Three dimensional model of mine tunnel can simulate the work scene at the ground mine，the network analysis based on it is very important for coal mine rescue.According to the network's characteristic of mine tunnel，the point and linear elements in the actual measurement data is abstracted to node-arc ADT，which corresponds to the construction of one-dimensional center line and two-dimensional double line tunnel.In the end，three-dimensional model of the mine tunnel is generated by using arch height of the section，wall height and topological relations to assemble the basic unit of laneway model and triangulation.Network analysis adopts Dijkstra algorithm which can adapt to topology changes，to optimize the traditional Dijkstra algorithm in reducing the search nodes and using the adjacency list storage structure，and then analyze the efficiency of the algorithm.Finally，a program is written to test the shortest path algorithm's analysis in the three dimensional model of mine tunnel with obstacles and make it roam in the model.The results show that the algorithm is fast and effective.

Shortest route algorithm，Dijkstra，3D model，Tunnel network，Roam

2015-02-03

車德福(1970—)，男，教授，博士。

TD178

A

1001-1250(2015)-04-273-05