Dijkstra算法在矿井通风计算中的应用

赵泓泉　杨溢　刘强

摘要： 矿井通风最大阻力路线计算是矿井通风设计的关键一环，是通风设备选择的主要依据。对于复杂通风网路的最大阻力路线计算，通常使用软件计算，文中设计了一种基于Dijkstra算法的矿井通风最大阻力路线编程计算方法，对该方法作了详细介绍，以期为编程计算矿井通风最大阻力路线提供一定的启发与帮助。

关键词： 矿井通风；最大阻力路线；Dijkstra算法

中图分类号：TD722 文献标识码：A 文章编号：1006-4311（2014）34-0028-02

0 引言

矿井通风总阻力，是指风流由进风井口到扇风机风硐（抽出式）或由扇风机风硐到回风井口（压入式）沿任一风路流动途中所产生的摩擦阻力和局部阻力的总和[1]。矿通风阻力计算是矿井通风设计中的关键一环，它是通风设备选择的主要依据。当通风系统比较复杂，在直观上难于判断哪条风路阻力最大时，就需要选择几条线路通过计算比较选出其中的最大者。通常情况下，是依靠个人经验来选择通风路线然后计算比较得出风路阻力最大者，这在一定程度存在较大误差，而对于多结点的复杂通风网路，遍历每条风路计算总风阻而后比较得出风路阻力最大者的这种精确算法，由于其计算量过大所以不适合人工计算，随着电子计算机的广泛应用，矿井通风总阻力计算与扇风机的选择计算，都可以用计算机进行，但无论是使用商务或者个人开发版的计算软件计算矿井通风总阻力值，对于单纯软件的使用者来说，一般不知道具体结果是如何计算得出的，其中的计算原理和计算误差都是一个不可知与不可控制的过程，本文针对以上问题，根据Dijkstra最短路径算法，扩展设计了一种编程实现全矿通风最大阻力路线计算的方法，就该方法的数学模型和具体算法作详细介绍，以期为编程计算全矿通风最大阻力路线提供一定的启发与帮助。

1 数学模型的建立

通风网络图的邻接矩阵：

以数学模型的方式完全描述一个矿井通风网络图是十分困难的，它涉及图论与风量分配基本定律的很多知识，其最终得出数学模型也是极其复杂的，但如果只针对全矿通风总阻力计算，从效能原则来看，通风网络图的邻接矩阵就是一个合理的数学模型，它既描述了风流的流向，给风路选择提供依据，又包括了每段风路的通风阻力值，可以通过计算所有风路的总阻力。

一个图G的结构，可以完全由结点之间的邻接关系来描述，这种关系可以通过一个矩阵来给出。

邻接矩阵：设G=（V，E）是一个有向有权图，V=m，E=n，称m阶方阵A（G）=（aij）为图G的邻接矩阵[2]。

其中，aij=权值/风阻（vi adj vj）时，aij=0（vi nadj vj或i=j时）

例如：图1为复杂角联通风网络图。

设ei（i=1，2，3…n），为权值。其邻接矩阵为：

2 算法详解

2.1 Dijkstra最短路径算法

迪杰斯特拉（E·W Dijkstra）提出了一个按路径长度递增的顺序产生最短路径的方法。此方法的基本思路是：把一个图中的所有顶点分为两组，第一组为已经确定最短路径的顶点集S，第二组为尚未确定最短路径的顶点集V-S，按最短路径长度递增的顺序逐个把第二组顶点加到第一组中去，直至从顶点v出发可以到达的所有顶点都包括在第一组中。在这个过程中，总保持从顶点v到第一组各顶点的最短路径都不大于从顶点v到第二组的任何顶点的最短路径长度。另外，每个顶点对应一个距离值，第一组的顶点对应的距离值就是从顶点v到此顶点的只包括第一组的顶点为中间顶点的最短路径长度[3]。

2.2 设计算法详解（Dijkstra最短路径算法的扩展）

本次论述主要算法运用的是Dijkstra算法的拓展，其思路与Dijkstra算法是一致的，只是在第一组顶点到第二组顶点的路径选择上作了一定的变化。让本来过程中，总保持从顶点v到第一组各顶点的最短路径都不大于从顶点v到第二组的任何顶点的最短路径长度，变为总保持从顶点v到第一组各顶点的最长路径都大于从顶点v到第二组的任何顶点的最长路径长度。具体将在以下进行详细解释。

2.2.1 建立MaM矩阵

为了方便计算机识别和计算，对于有N个节点的通风网络图而言，我们首先建立一个（N×N+3）的矩阵，这里称其为MaM矩阵（Maximum resistance of ventilation routes Matrix），其中MaM矩阵中所包含的前N阶方阵是所需计算的通风网络图生成的邻接矩阵，这个邻接矩阵再合并上方便计算机识别计算对象的N×3阶矩阵后，所构成的增广矩阵就是真正意义上程序中所能看到的MaM矩阵，从编程角度来说MaM矩阵实际上是一个二维数组，其使用上和矩阵无太大差别，这里就不做过多区别，以下均称为MaM矩阵。（图2）

为了更好地说明问题，引入联组的概念。上（始）节点和直接与其相连的所有下（末）结点所构成的一个集合，称为联组。联组由上（始）结点号来命名[4]。图中，v1～vn是结点；1～n是联组名。

CP（Calculation Point）计算点，辅助程序记录结点所对应联组数，同时也是程序识别结点是否计算完成找出最大权值联组的标志，第i行对应的CP表示的是与i联组相邻下一联组的数量，也就是Vi行中，非0元的个数。当计算程序遍历i联组中各个元素时，CP值就会改变，每次计算完成一个联组CP值自减1，当遍历完i联组所有元素时CP值为0，表示已经计算找出结点全部联组中最大权值联组，计算结束。

MV（Maximum Value）结点最大权弧的权值，其保存了该结点所对应当前最大权弧的权值，即网络中某通风节点所对应当前计算次数下，最大阻力路线的总阻力值。例如，Vi是第i个结点，第i行对应的mi储存的是从回风结点到第i个结点当前计算次数下最大通风阻力累计值。也就是说，在当前计算次数下，从回风结点开始按风流路线到该结点无论中间经历多少个结点，多少种路线，其最大阻力路线的累计通风阻力值就是MV。特别的，只有当该结点对应的所有联组计算完成时（结点对应CP=0时），其对应的MV才是该结点真正的最大权弧的权值。endprint

JP（Joint Point）连接点，指当前计算次数下，结点所对应当前最大权弧中与结点相邻的下一结点编号，也是结点对应当前最大权值联组的联组名。例如，第i行对应的JP是第i个结点的联组中与结点Vi构成当前最大阻力路线的下一联组的联组名（或编号），它是计算程序识别最大通风阻力路线的线索和依据。特别的，只有当该结点对应的所有联组计算完成时（结点对应CP=0时），其对应的JP才是该结点最大权弧中与该结点相邻的下一结点编号。

2.2.2 解算MaM矩阵

当建立好MaM矩阵以后，首先找到回风结点（MaM矩阵中行向量为0的行，该行所对应的结点为回风结点），由回风结点开始，用回风结点的MV值依次与其邻接结点的临接权值进行累加，将累加值与邻接结点的MV值（结点i，即mi）将进行比较，将较大者存入邻接结点的MV值（如结点i，即mi）中，回风结点的结点编号存入结点的JP值（如结点i，即ji）中。每计算完一次，结点的CP值（如结点i，即ci）自减1。

计算完与回风结点临接的所有结点之后，在MaM矩阵中找到CP值为0的结点，即CP列向量中，0元所在的行的行号（如结点j）。由该结点（如结点j）开始，依次与其邻接结点（如结点k）的临接权值进行累加，将累加值与邻接结点（如结点k）的MV值（结点k，即mk）将进行比较，将较大者存入邻接结点的MV值（如结点k，即mk）中，较大者的结点编号存入结点的JP值（如结点k，即jk）中。每计算完一次，结点的CP值（如结点k，即ck）自减1。重复该步骤，层层向上，直到MaM矩阵中CP列向量为0，全部计算结束。

全部计算结束后，在MaM矩阵中MV列向量中找出最大的元，该元就是最大权路线的权值（通风最大阻力路线阻力值），而该元所在行对应结点就是最大权路线的起始结点，根据起始结点与起始结点对应的JP值就可找出，起始结点的最大权弧中与起始结点相邻的下一结点，同理，依次往下寻找邻接结点，直到最后一个邻接结点是回风结点，路线寻找完毕。

3 结论

本文设计了一种基于Dijkstra算法的矿井通风最大阻力路线编程计算方法，通过对该方法的详细介绍，给编程计算全矿通风最大阻力路线提供了一定的启发。同时，也为通风计算软件的设计者和使用者对改进和了解矿井通风最大阻力路线计算程序编程提供了一定的思路。

参考文献：

[1]支学艺，何锦龙编.矿井通风与防尘[M].北京：化学工业出版社，2009：203.

[2]李恕和，王义章编.矿井通风网络图论[M].北京：煤炭工业出版社，1984：24.

[3]郭芳，曹桂琴编.数据结构基础[M].大连：大连理工大学出版社，2004：102.

[4]沈斐敏主编.矿井通风微机程序设计与应用[M].北京：煤炭工业出版社，1995：2.endprint

JP（Joint Point）连接点，指当前计算次数下，结点所对应当前最大权弧中与结点相邻的下一结点编号，也是结点对应当前最大权值联组的联组名。例如，第i行对应的JP是第i个结点的联组中与结点Vi构成当前最大阻力路线的下一联组的联组名（或编号），它是计算程序识别最大通风阻力路线的线索和依据。特别的，只有当该结点对应的所有联组计算完成时（结点对应CP=0时），其对应的JP才是该结点最大权弧中与该结点相邻的下一结点编号。

2.2.2 解算MaM矩阵

当建立好MaM矩阵以后，首先找到回风结点（MaM矩阵中行向量为0的行，该行所对应的结点为回风结点），由回风结点开始，用回风结点的MV值依次与其邻接结点的临接权值进行累加，将累加值与邻接结点的MV值（结点i，即mi）将进行比较，将较大者存入邻接结点的MV值（如结点i，即mi）中，回风结点的结点编号存入结点的JP值（如结点i，即ji）中。每计算完一次，结点的CP值（如结点i，即ci）自减1。

计算完与回风结点临接的所有结点之后，在MaM矩阵中找到CP值为0的结点，即CP列向量中，0元所在的行的行号（如结点j）。由该结点（如结点j）开始，依次与其邻接结点（如结点k）的临接权值进行累加，将累加值与邻接结点（如结点k）的MV值（结点k，即mk）将进行比较，将较大者存入邻接结点的MV值（如结点k，即mk）中，较大者的结点编号存入结点的JP值（如结点k，即jk）中。每计算完一次，结点的CP值（如结点k，即ck）自减1。重复该步骤，层层向上，直到MaM矩阵中CP列向量为0，全部计算结束。

全部计算结束后，在MaM矩阵中MV列向量中找出最大的元，该元就是最大权路线的权值（通风最大阻力路线阻力值），而该元所在行对应结点就是最大权路线的起始结点，根据起始结点与起始结点对应的JP值就可找出，起始结点的最大权弧中与起始结点相邻的下一结点，同理，依次往下寻找邻接结点，直到最后一个邻接结点是回风结点，路线寻找完毕。

3 结论

本文设计了一种基于Dijkstra算法的矿井通风最大阻力路线编程计算方法，通过对该方法的详细介绍，给编程计算全矿通风最大阻力路线提供了一定的启发。同时，也为通风计算软件的设计者和使用者对改进和了解矿井通风最大阻力路线计算程序编程提供了一定的思路。

参考文献：

[1]支学艺，何锦龙编.矿井通风与防尘[M].北京：化学工业出版社，2009：203.

[2]李恕和，王义章编.矿井通风网络图论[M].北京：煤炭工业出版社，1984：24.

[3]郭芳，曹桂琴编.数据结构基础[M].大连：大连理工大学出版社，2004：102.

[4]沈斐敏主编.矿井通风微机程序设计与应用[M].北京：煤炭工业出版社，1995：2.endprint

JP（Joint Point）连接点，指当前计算次数下，结点所对应当前最大权弧中与结点相邻的下一结点编号，也是结点对应当前最大权值联组的联组名。例如，第i行对应的JP是第i个结点的联组中与结点Vi构成当前最大阻力路线的下一联组的联组名（或编号），它是计算程序识别最大通风阻力路线的线索和依据。特别的，只有当该结点对应的所有联组计算完成时（结点对应CP=0时），其对应的JP才是该结点最大权弧中与该结点相邻的下一结点编号。

2.2.2 解算MaM矩阵

当建立好MaM矩阵以后，首先找到回风结点（MaM矩阵中行向量为0的行，该行所对应的结点为回风结点），由回风结点开始，用回风结点的MV值依次与其邻接结点的临接权值进行累加，将累加值与邻接结点的MV值（结点i，即mi）将进行比较，将较大者存入邻接结点的MV值（如结点i，即mi）中，回风结点的结点编号存入结点的JP值（如结点i，即ji）中。每计算完一次，结点的CP值（如结点i，即ci）自减1。

计算完与回风结点临接的所有结点之后，在MaM矩阵中找到CP值为0的结点，即CP列向量中，0元所在的行的行号（如结点j）。由该结点（如结点j）开始，依次与其邻接结点（如结点k）的临接权值进行累加，将累加值与邻接结点（如结点k）的MV值（结点k，即mk）将进行比较，将较大者存入邻接结点的MV值（如结点k，即mk）中，较大者的结点编号存入结点的JP值（如结点k，即jk）中。每计算完一次，结点的CP值（如结点k，即ck）自减1。重复该步骤，层层向上，直到MaM矩阵中CP列向量为0，全部计算结束。

全部计算结束后，在MaM矩阵中MV列向量中找出最大的元，该元就是最大权路线的权值（通风最大阻力路线阻力值），而该元所在行对应结点就是最大权路线的起始结点，根据起始结点与起始结点对应的JP值就可找出，起始结点的最大权弧中与起始结点相邻的下一结点，同理，依次往下寻找邻接结点，直到最后一个邻接结点是回风结点，路线寻找完毕。

3 结论

本文设计了一种基于Dijkstra算法的矿井通风最大阻力路线编程计算方法，通过对该方法的详细介绍，给编程计算全矿通风最大阻力路线提供了一定的启发。同时，也为通风计算软件的设计者和使用者对改进和了解矿井通风最大阻力路线计算程序编程提供了一定的思路。

参考文献：

[1]支学艺，何锦龙编.矿井通风与防尘[M].北京：化学工业出版社，2009：203.

[2]李恕和，王义章编.矿井通风网络图论[M].北京：煤炭工业出版社，1984：24.

[3]郭芳，曹桂琴编.数据结构基础[M].大连：大连理工大学出版社，2004：102.

[4]沈斐敏主编.矿井通风微机程序设计与应用[M].北京：煤炭工业出版社，1995：2.endprint