Dijkstra算法在礦井通風(fēng)計(jì)算中的應(yīng)用

趙泓泉　楊溢　劉強(qiáng)

摘要： 礦井通風(fēng)最大阻力路線計(jì)算是礦井通風(fēng)設(shè)計(jì)的關(guān)鍵一環(huán)，是通風(fēng)設(shè)備選擇的主要依據(jù)。對于復(fù)雜通風(fēng)網(wǎng)路的最大阻力路線計(jì)算，通常使用軟件計(jì)算，文中設(shè)計(jì)了一種基于Dijkstra算法的礦井通風(fēng)最大阻力路線編程計(jì)算方法，對該方法作了詳細(xì)介紹，以期為編程計(jì)算礦井通風(fēng)最大阻力路線提供一定的啟發(fā)與幫助。

關(guān)鍵詞： 礦井通風(fēng)；最大阻力路線；Dijkstra算法

中圖分類號(hào)：TD722 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2014）34-0028-02

0 引言

礦井通風(fēng)總阻力，是指風(fēng)流由進(jìn)風(fēng)井口到扇風(fēng)機(jī)風(fēng)硐（抽出式）或由扇風(fēng)機(jī)風(fēng)硐到回風(fēng)井口（壓入式）沿任一風(fēng)路流動(dòng)途中所產(chǎn)生的摩擦阻力和局部阻力的總和[1]。礦通風(fēng)阻力計(jì)算是礦井通風(fēng)設(shè)計(jì)中的關(guān)鍵一環(huán)，它是通風(fēng)設(shè)備選擇的主要依據(jù)。當(dāng)通風(fēng)系統(tǒng)比較復(fù)雜，在直觀上難于判斷哪條風(fēng)路阻力最大時(shí)，就需要選擇幾條線路通過計(jì)算比較選出其中的最大者。通常情況下，是依靠個(gè)人經(jīng)驗(yàn)來選擇通風(fēng)路線然后計(jì)算比較得出風(fēng)路阻力最大者，這在一定程度存在較大誤差，而對于多結(jié)點(diǎn)的復(fù)雜通風(fēng)網(wǎng)路，遍歷每條風(fēng)路計(jì)算總風(fēng)阻而后比較得出風(fēng)路阻力最大者的這種精確算法，由于其計(jì)算量過大所以不適合人工計(jì)算，隨著電子計(jì)算機(jī)的廣泛應(yīng)用，礦井通風(fēng)總阻力計(jì)算與扇風(fēng)機(jī)的選擇計(jì)算，都可以用計(jì)算機(jī)進(jìn)行，但無論是使用商務(wù)或者個(gè)人開發(fā)版的計(jì)算軟件計(jì)算礦井通風(fēng)總阻力值，對于單純軟件的使用者來說，一般不知道具體結(jié)果是如何計(jì)算得出的，其中的計(jì)算原理和計(jì)算誤差都是一個(gè)不可知與不可控制的過程，本文針對以上問題，根據(jù)Dijkstra最短路徑算法，擴(kuò)展設(shè)計(jì)了一種編程實(shí)現(xiàn)全礦通風(fēng)最大阻力路線計(jì)算的方法，就該方法的數(shù)學(xué)模型和具體算法作詳細(xì)介紹，以期為編程計(jì)算全礦通風(fēng)最大阻力路線提供一定的啟發(fā)與幫助。

1 數(shù)學(xué)模型的建立

通風(fēng)網(wǎng)絡(luò)圖的鄰接矩陣：

以數(shù)學(xué)模型的方式完全描述一個(gè)礦井通風(fēng)網(wǎng)絡(luò)圖是十分困難的，它涉及圖論與風(fēng)量分配基本定律的很多知識(shí)，其最終得出數(shù)學(xué)模型也是極其復(fù)雜的，但如果只針對全礦通風(fēng)總阻力計(jì)算，從效能原則來看，通風(fēng)網(wǎng)絡(luò)圖的鄰接矩陣就是一個(gè)合理的數(shù)學(xué)模型，它既描述了風(fēng)流的流向，給風(fēng)路選擇提供依據(jù)，又包括了每段風(fēng)路的通風(fēng)阻力值，可以通過計(jì)算所有風(fēng)路的總阻力。

一個(gè)圖G的結(jié)構(gòu)，可以完全由結(jié)點(diǎn)之間的鄰接關(guān)系來描述，這種關(guān)系可以通過一個(gè)矩陣來給出。

鄰接矩陣：設(shè)G=（V，E）是一個(gè)有向有權(quán)圖，V=m，E=n，稱m階方陣A（G）=（aij）為圖G的鄰接矩陣[2]。

其中，aij=權(quán)值/風(fēng)阻（vi adj vj）時(shí)，aij=0（vi nadj vj或i=j時(shí)）

例如：圖1為復(fù)雜角聯(lián)通風(fēng)網(wǎng)絡(luò)圖。

設(shè)ei（i=1，2，3…n），為權(quán)值。其鄰接矩陣為：

2 算法詳解

2.1 Dijkstra最短路徑算法

迪杰斯特拉（E·W Dijkstra）提出了一個(gè)按路徑長度遞增的順序產(chǎn)生最短路徑的方法。此方法的基本思路是：把一個(gè)圖中的所有頂點(diǎn)分為兩組，第一組為已經(jīng)確定最短路徑的頂點(diǎn)集S，第二組為尚未確定最短路徑的頂點(diǎn)集V-S，按最短路徑長度遞增的順序逐個(gè)把第二組頂點(diǎn)加到第一組中去，直至從頂點(diǎn)v出發(fā)可以到達(dá)的所有頂點(diǎn)都包括在第一組中。在這個(gè)過程中，總保持從頂點(diǎn)v到第一組各頂點(diǎn)的最短路徑都不大于從頂點(diǎn)v到第二組的任何頂點(diǎn)的最短路徑長度。另外，每個(gè)頂點(diǎn)對應(yīng)一個(gè)距離值，第一組的頂點(diǎn)對應(yīng)的距離值就是從頂點(diǎn)v到此頂點(diǎn)的只包括第一組的頂點(diǎn)為中間頂點(diǎn)的最短路徑長度[3]。

2.2 設(shè)計(jì)算法詳解（Dijkstra最短路徑算法的擴(kuò)展）

本次論述主要算法運(yùn)用的是Dijkstra算法的拓展，其思路與Dijkstra算法是一致的，只是在第一組頂點(diǎn)到第二組頂點(diǎn)的路徑選擇上作了一定的變化。讓本來過程中，總保持從頂點(diǎn)v到第一組各頂點(diǎn)的最短路徑都不大于從頂點(diǎn)v到第二組的任何頂點(diǎn)的最短路徑長度，變?yōu)榭偙３謴捻旤c(diǎn)v到第一組各頂點(diǎn)的最長路徑都大于從頂點(diǎn)v到第二組的任何頂點(diǎn)的最長路徑長度。具體將在以下進(jìn)行詳細(xì)解釋。

2.2.1 建立MaM矩陣

為了方便計(jì)算機(jī)識(shí)別和計(jì)算，對于有N個(gè)節(jié)點(diǎn)的通風(fēng)網(wǎng)絡(luò)圖而言，我們首先建立一個(gè)（N×N+3）的矩陣，這里稱其為MaM矩陣（Maximum resistance of ventilation routes Matrix），其中MaM矩陣中所包含的前N階方陣是所需計(jì)算的通風(fēng)網(wǎng)絡(luò)圖生成的鄰接矩陣，這個(gè)鄰接矩陣再合并上方便計(jì)算機(jī)識(shí)別計(jì)算對象的N×3階矩陣后，所構(gòu)成的增廣矩陣就是真正意義上程序中所能看到的MaM矩陣，從編程角度來說MaM矩陣實(shí)際上是一個(gè)二維數(shù)組，其使用上和矩陣無太大差別，這里就不做過多區(qū)別，以下均稱為MaM矩陣。（圖2）

為了更好地說明問題，引入聯(lián)組的概念。上（始）節(jié)點(diǎn)和直接與其相連的所有下（末）結(jié)點(diǎn)所構(gòu)成的一個(gè)集合，稱為聯(lián)組。聯(lián)組由上（始）結(jié)點(diǎn)號(hào)來命名[4]。圖中，v1～vn是結(jié)點(diǎn)；1～n是聯(lián)組名。

CP（Calculation Point）計(jì)算點(diǎn)，輔助程序記錄結(jié)點(diǎn)所對應(yīng)聯(lián)組數(shù)，同時(shí)也是程序識(shí)別結(jié)點(diǎn)是否計(jì)算完成找出最大權(quán)值聯(lián)組的標(biāo)志，第i行對應(yīng)的CP表示的是與i聯(lián)組相鄰下一聯(lián)組的數(shù)量，也就是Vi行中，非0元的個(gè)數(shù)。當(dāng)計(jì)算程序遍歷i聯(lián)組中各個(gè)元素時(shí)，CP值就會(huì)改變，每次計(jì)算完成一個(gè)聯(lián)組CP值自減1，當(dāng)遍歷完i聯(lián)組所有元素時(shí)CP值為0，表示已經(jīng)計(jì)算找出結(jié)點(diǎn)全部聯(lián)組中最大權(quán)值聯(lián)組，計(jì)算結(jié)束。

MV（Maximum Value）結(jié)點(diǎn)最大權(quán)弧的權(quán)值，其保存了該結(jié)點(diǎn)所對應(yīng)當(dāng)前最大權(quán)弧的權(quán)值，即網(wǎng)絡(luò)中某通風(fēng)節(jié)點(diǎn)所對應(yīng)當(dāng)前計(jì)算次數(shù)下，最大阻力路線的總阻力值。例如，Vi是第i個(gè)結(jié)點(diǎn)，第i行對應(yīng)的mi儲(chǔ)存的是從回風(fēng)結(jié)點(diǎn)到第i個(gè)結(jié)點(diǎn)當(dāng)前計(jì)算次數(shù)下最大通風(fēng)阻力累計(jì)值。也就是說，在當(dāng)前計(jì)算次數(shù)下，從回風(fēng)結(jié)點(diǎn)開始按風(fēng)流路線到該結(jié)點(diǎn)無論中間經(jīng)歷多少個(gè)結(jié)點(diǎn)，多少種路線，其最大阻力路線的累計(jì)通風(fēng)阻力值就是MV。特別的，只有當(dāng)該結(jié)點(diǎn)對應(yīng)的所有聯(lián)組計(jì)算完成時(shí)（結(jié)點(diǎn)對應(yīng)CP=0時(shí)），其對應(yīng)的MV才是該結(jié)點(diǎn)真正的最大權(quán)弧的權(quán)值。endprint

JP（Joint Point）連接點(diǎn)，指當(dāng)前計(jì)算次數(shù)下，結(jié)點(diǎn)所對應(yīng)當(dāng)前最大權(quán)弧中與結(jié)點(diǎn)相鄰的下一結(jié)點(diǎn)編號(hào)，也是結(jié)點(diǎn)對應(yīng)當(dāng)前最大權(quán)值聯(lián)組的聯(lián)組名。例如，第i行對應(yīng)的JP是第i個(gè)結(jié)點(diǎn)的聯(lián)組中與結(jié)點(diǎn)Vi構(gòu)成當(dāng)前最大阻力路線的下一聯(lián)組的聯(lián)組名（或編號(hào)），它是計(jì)算程序識(shí)別最大通風(fēng)阻力路線的線索和依據(jù)。特別的，只有當(dāng)該結(jié)點(diǎn)對應(yīng)的所有聯(lián)組計(jì)算完成時(shí)（結(jié)點(diǎn)對應(yīng)CP=0時(shí)），其對應(yīng)的JP才是該結(jié)點(diǎn)最大權(quán)弧中與該結(jié)點(diǎn)相鄰的下一結(jié)點(diǎn)編號(hào)。

2.2.2 解算MaM矩陣

當(dāng)建立好MaM矩陣以后，首先找到回風(fēng)結(jié)點(diǎn)（MaM矩陣中行向量為0的行，該行所對應(yīng)的結(jié)點(diǎn)為回風(fēng)結(jié)點(diǎn)），由回風(fēng)結(jié)點(diǎn)開始，用回風(fēng)結(jié)點(diǎn)的MV值依次與其鄰接結(jié)點(diǎn)的臨接權(quán)值進(jìn)行累加，將累加值與鄰接結(jié)點(diǎn)的MV值（結(jié)點(diǎn)i，即mi）將進(jìn)行比較，將較大者存入鄰接結(jié)點(diǎn)的MV值（如結(jié)點(diǎn)i，即mi）中，回風(fēng)結(jié)點(diǎn)的結(jié)點(diǎn)編號(hào)存入結(jié)點(diǎn)的JP值（如結(jié)點(diǎn)i，即ji）中。每計(jì)算完一次，結(jié)點(diǎn)的CP值（如結(jié)點(diǎn)i，即ci）自減1。

計(jì)算完與回風(fēng)結(jié)點(diǎn)臨接的所有結(jié)點(diǎn)之后，在MaM矩陣中找到CP值為0的結(jié)點(diǎn)，即CP列向量中，0元所在的行的行號(hào)（如結(jié)點(diǎn)j）。由該結(jié)點(diǎn)（如結(jié)點(diǎn)j）開始，依次與其鄰接結(jié)點(diǎn)（如結(jié)點(diǎn)k）的臨接權(quán)值進(jìn)行累加，將累加值與鄰接結(jié)點(diǎn)（如結(jié)點(diǎn)k）的MV值（結(jié)點(diǎn)k，即mk）將進(jìn)行比較，將較大者存入鄰接結(jié)點(diǎn)的MV值（如結(jié)點(diǎn)k，即mk）中，較大者的結(jié)點(diǎn)編號(hào)存入結(jié)點(diǎn)的JP值（如結(jié)點(diǎn)k，即jk）中。每計(jì)算完一次，結(jié)點(diǎn)的CP值（如結(jié)點(diǎn)k，即ck）自減1。重復(fù)該步驟，層層向上，直到MaM矩陣中CP列向量為0，全部計(jì)算結(jié)束。

全部計(jì)算結(jié)束后，在MaM矩陣中MV列向量中找出最大的元，該元就是最大權(quán)路線的權(quán)值（通風(fēng)最大阻力路線阻力值），而該元所在行對應(yīng)結(jié)點(diǎn)就是最大權(quán)路線的起始結(jié)點(diǎn)，根據(jù)起始結(jié)點(diǎn)與起始結(jié)點(diǎn)對應(yīng)的JP值就可找出，起始結(jié)點(diǎn)的最大權(quán)弧中與起始結(jié)點(diǎn)相鄰的下一結(jié)點(diǎn)，同理，依次往下尋找鄰接結(jié)點(diǎn)，直到最后一個(gè)鄰接結(jié)點(diǎn)是回風(fēng)結(jié)點(diǎn)，路線尋找完畢。

3 結(jié)論

本文設(shè)計(jì)了一種基于Dijkstra算法的礦井通風(fēng)最大阻力路線編程計(jì)算方法，通過對該方法的詳細(xì)介紹，給編程計(jì)算全礦通風(fēng)最大阻力路線提供了一定的啟發(fā)。同時(shí)，也為通風(fēng)計(jì)算軟件的設(shè)計(jì)者和使用者對改進(jìn)和了解礦井通風(fēng)最大阻力路線計(jì)算程序編程提供了一定的思路。

參考文獻(xiàn)：

[1]支學(xué)藝，何錦龍編.礦井通風(fēng)與防塵[M].北京：化學(xué)工業(yè)出版社，2009：203.

[2]李恕和，王義章編.礦井通風(fēng)網(wǎng)絡(luò)圖論[M].北京：煤炭工業(yè)出版社，1984：24.

[3]郭芳，曹桂琴編.數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)[M].大連：大連理工大學(xué)出版社，2004：102.

[4]沈斐敏主編.礦井通風(fēng)微機(jī)程序設(shè)計(jì)與應(yīng)用[M].北京：煤炭工業(yè)出版社，1995：2.endprint

JP（Joint Point）連接點(diǎn)，指當(dāng)前計(jì)算次數(shù)下，結(jié)點(diǎn)所對應(yīng)當(dāng)前最大權(quán)弧中與結(jié)點(diǎn)相鄰的下一結(jié)點(diǎn)編號(hào)，也是結(jié)點(diǎn)對應(yīng)當(dāng)前最大權(quán)值聯(lián)組的聯(lián)組名。例如，第i行對應(yīng)的JP是第i個(gè)結(jié)點(diǎn)的聯(lián)組中與結(jié)點(diǎn)Vi構(gòu)成當(dāng)前最大阻力路線的下一聯(lián)組的聯(lián)組名（或編號(hào)），它是計(jì)算程序識(shí)別最大通風(fēng)阻力路線的線索和依據(jù)。特別的，只有當(dāng)該結(jié)點(diǎn)對應(yīng)的所有聯(lián)組計(jì)算完成時(shí)（結(jié)點(diǎn)對應(yīng)CP=0時(shí)），其對應(yīng)的JP才是該結(jié)點(diǎn)最大權(quán)弧中與該結(jié)點(diǎn)相鄰的下一結(jié)點(diǎn)編號(hào)。

2.2.2 解算MaM矩陣

當(dāng)建立好MaM矩陣以后，首先找到回風(fēng)結(jié)點(diǎn)（MaM矩陣中行向量為0的行，該行所對應(yīng)的結(jié)點(diǎn)為回風(fēng)結(jié)點(diǎn)），由回風(fēng)結(jié)點(diǎn)開始，用回風(fēng)結(jié)點(diǎn)的MV值依次與其鄰接結(jié)點(diǎn)的臨接權(quán)值進(jìn)行累加，將累加值與鄰接結(jié)點(diǎn)的MV值（結(jié)點(diǎn)i，即mi）將進(jìn)行比較，將較大者存入鄰接結(jié)點(diǎn)的MV值（如結(jié)點(diǎn)i，即mi）中，回風(fēng)結(jié)點(diǎn)的結(jié)點(diǎn)編號(hào)存入結(jié)點(diǎn)的JP值（如結(jié)點(diǎn)i，即ji）中。每計(jì)算完一次，結(jié)點(diǎn)的CP值（如結(jié)點(diǎn)i，即ci）自減1。

計(jì)算完與回風(fēng)結(jié)點(diǎn)臨接的所有結(jié)點(diǎn)之后，在MaM矩陣中找到CP值為0的結(jié)點(diǎn)，即CP列向量中，0元所在的行的行號(hào)（如結(jié)點(diǎn)j）。由該結(jié)點(diǎn)（如結(jié)點(diǎn)j）開始，依次與其鄰接結(jié)點(diǎn)（如結(jié)點(diǎn)k）的臨接權(quán)值進(jìn)行累加，將累加值與鄰接結(jié)點(diǎn)（如結(jié)點(diǎn)k）的MV值（結(jié)點(diǎn)k，即mk）將進(jìn)行比較，將較大者存入鄰接結(jié)點(diǎn)的MV值（如結(jié)點(diǎn)k，即mk）中，較大者的結(jié)點(diǎn)編號(hào)存入結(jié)點(diǎn)的JP值（如結(jié)點(diǎn)k，即jk）中。每計(jì)算完一次，結(jié)點(diǎn)的CP值（如結(jié)點(diǎn)k，即ck）自減1。重復(fù)該步驟，層層向上，直到MaM矩陣中CP列向量為0，全部計(jì)算結(jié)束。

全部計(jì)算結(jié)束后，在MaM矩陣中MV列向量中找出最大的元，該元就是最大權(quán)路線的權(quán)值（通風(fēng)最大阻力路線阻力值），而該元所在行對應(yīng)結(jié)點(diǎn)就是最大權(quán)路線的起始結(jié)點(diǎn)，根據(jù)起始結(jié)點(diǎn)與起始結(jié)點(diǎn)對應(yīng)的JP值就可找出，起始結(jié)點(diǎn)的最大權(quán)弧中與起始結(jié)點(diǎn)相鄰的下一結(jié)點(diǎn)，同理，依次往下尋找鄰接結(jié)點(diǎn)，直到最后一個(gè)鄰接結(jié)點(diǎn)是回風(fēng)結(jié)點(diǎn)，路線尋找完畢。

3 結(jié)論

本文設(shè)計(jì)了一種基于Dijkstra算法的礦井通風(fēng)最大阻力路線編程計(jì)算方法，通過對該方法的詳細(xì)介紹，給編程計(jì)算全礦通風(fēng)最大阻力路線提供了一定的啟發(fā)。同時(shí)，也為通風(fēng)計(jì)算軟件的設(shè)計(jì)者和使用者對改進(jìn)和了解礦井通風(fēng)最大阻力路線計(jì)算程序編程提供了一定的思路。

參考文獻(xiàn)：

[1]支學(xué)藝，何錦龍編.礦井通風(fēng)與防塵[M].北京：化學(xué)工業(yè)出版社，2009：203.

[2]李恕和，王義章編.礦井通風(fēng)網(wǎng)絡(luò)圖論[M].北京：煤炭工業(yè)出版社，1984：24.

[3]郭芳，曹桂琴編.數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)[M].大連：大連理工大學(xué)出版社，2004：102.

[4]沈斐敏主編.礦井通風(fēng)微機(jī)程序設(shè)計(jì)與應(yīng)用[M].北京：煤炭工業(yè)出版社，1995：2.endprint

JP（Joint Point）連接點(diǎn)，指當(dāng)前計(jì)算次數(shù)下，結(jié)點(diǎn)所對應(yīng)當(dāng)前最大權(quán)弧中與結(jié)點(diǎn)相鄰的下一結(jié)點(diǎn)編號(hào)，也是結(jié)點(diǎn)對應(yīng)當(dāng)前最大權(quán)值聯(lián)組的聯(lián)組名。例如，第i行對應(yīng)的JP是第i個(gè)結(jié)點(diǎn)的聯(lián)組中與結(jié)點(diǎn)Vi構(gòu)成當(dāng)前最大阻力路線的下一聯(lián)組的聯(lián)組名（或編號(hào)），它是計(jì)算程序識(shí)別最大通風(fēng)阻力路線的線索和依據(jù)。特別的，只有當(dāng)該結(jié)點(diǎn)對應(yīng)的所有聯(lián)組計(jì)算完成時(shí)（結(jié)點(diǎn)對應(yīng)CP=0時(shí)），其對應(yīng)的JP才是該結(jié)點(diǎn)最大權(quán)弧中與該結(jié)點(diǎn)相鄰的下一結(jié)點(diǎn)編號(hào)。

2.2.2 解算MaM矩陣

當(dāng)建立好MaM矩陣以后，首先找到回風(fēng)結(jié)點(diǎn)（MaM矩陣中行向量為0的行，該行所對應(yīng)的結(jié)點(diǎn)為回風(fēng)結(jié)點(diǎn)），由回風(fēng)結(jié)點(diǎn)開始，用回風(fēng)結(jié)點(diǎn)的MV值依次與其鄰接結(jié)點(diǎn)的臨接權(quán)值進(jìn)行累加，將累加值與鄰接結(jié)點(diǎn)的MV值（結(jié)點(diǎn)i，即mi）將進(jìn)行比較，將較大者存入鄰接結(jié)點(diǎn)的MV值（如結(jié)點(diǎn)i，即mi）中，回風(fēng)結(jié)點(diǎn)的結(jié)點(diǎn)編號(hào)存入結(jié)點(diǎn)的JP值（如結(jié)點(diǎn)i，即ji）中。每計(jì)算完一次，結(jié)點(diǎn)的CP值（如結(jié)點(diǎn)i，即ci）自減1。

計(jì)算完與回風(fēng)結(jié)點(diǎn)臨接的所有結(jié)點(diǎn)之后，在MaM矩陣中找到CP值為0的結(jié)點(diǎn)，即CP列向量中，0元所在的行的行號(hào)（如結(jié)點(diǎn)j）。由該結(jié)點(diǎn)（如結(jié)點(diǎn)j）開始，依次與其鄰接結(jié)點(diǎn)（如結(jié)點(diǎn)k）的臨接權(quán)值進(jìn)行累加，將累加值與鄰接結(jié)點(diǎn)（如結(jié)點(diǎn)k）的MV值（結(jié)點(diǎn)k，即mk）將進(jìn)行比較，將較大者存入鄰接結(jié)點(diǎn)的MV值（如結(jié)點(diǎn)k，即mk）中，較大者的結(jié)點(diǎn)編號(hào)存入結(jié)點(diǎn)的JP值（如結(jié)點(diǎn)k，即jk）中。每計(jì)算完一次，結(jié)點(diǎn)的CP值（如結(jié)點(diǎn)k，即ck）自減1。重復(fù)該步驟，層層向上，直到MaM矩陣中CP列向量為0，全部計(jì)算結(jié)束。

全部計(jì)算結(jié)束后，在MaM矩陣中MV列向量中找出最大的元，該元就是最大權(quán)路線的權(quán)值（通風(fēng)最大阻力路線阻力值），而該元所在行對應(yīng)結(jié)點(diǎn)就是最大權(quán)路線的起始結(jié)點(diǎn)，根據(jù)起始結(jié)點(diǎn)與起始結(jié)點(diǎn)對應(yīng)的JP值就可找出，起始結(jié)點(diǎn)的最大權(quán)弧中與起始結(jié)點(diǎn)相鄰的下一結(jié)點(diǎn)，同理，依次往下尋找鄰接結(jié)點(diǎn)，直到最后一個(gè)鄰接結(jié)點(diǎn)是回風(fēng)結(jié)點(diǎn)，路線尋找完畢。

3 結(jié)論

本文設(shè)計(jì)了一種基于Dijkstra算法的礦井通風(fēng)最大阻力路線編程計(jì)算方法，通過對該方法的詳細(xì)介紹，給編程計(jì)算全礦通風(fēng)最大阻力路線提供了一定的啟發(fā)。同時(shí)，也為通風(fēng)計(jì)算軟件的設(shè)計(jì)者和使用者對改進(jìn)和了解礦井通風(fēng)最大阻力路線計(jì)算程序編程提供了一定的思路。

參考文獻(xiàn)：

[1]支學(xué)藝，何錦龍編.礦井通風(fēng)與防塵[M].北京：化學(xué)工業(yè)出版社，2009：203.

[2]李恕和，王義章編.礦井通風(fēng)網(wǎng)絡(luò)圖論[M].北京：煤炭工業(yè)出版社，1984：24.

[3]郭芳，曹桂琴編.數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)[M].大連：大連理工大學(xué)出版社，2004：102.

[4]沈斐敏主編.礦井通風(fēng)微機(jī)程序設(shè)計(jì)與應(yīng)用[M].北京：煤炭工業(yè)出版社，1995：2.endprint