最短供水路线的矩阵求法  

Shortest route of supplying water's matrix method

作　　者：樊开青[1] 樊赵兵[2] 

机构地区：[1]南京工业大学城市建设与安全环境学院,江苏南京210009 [2]哈尔滨工程大学理学院,黑龙江哈尔滨150001

出　　处：《哈尔滨工程大学学报》2005年第2期269-271,共3页Journal of Harbin Engineering University

摘　　要：在一定条件下简单有向图的完全关联矩阵中列向量线性相关时,它们对应的边构成回路.因此,通过判断简单有向图的完全关系矩阵中列向量组的线性相关性,可以求出简单有向图的最小生成树.给出了该算法实现的基本框图,从而能够快速简便地寻找最短供水路线.最后,比较了文中的最小生成树算法和经典的Dijkstra算法的收敛速度,证明了在简单有向图的节点数较大时,文中的算法收敛较快.In some condition, if column vectors in a complete incidence matrix are not linearly independent, these sides which are denoted by the column vectors formed a circuit. To quickly obtain the shortest route for supplying water, a theory and related algorithms were put forward based on determining the linear correlation of column vectors in a complete incidence matrix. The speeds of this algorithms of obtaining the min-spanning tree and the Dijkstra algorithms were compared. And when the number of node is large, this algorithm converged fastly.

关 键 词：最短供水路线 最小生成树 完全关联矩阵 

分 类 号：O157.5[理学—数学]