最短路径的可达矩阵算法  

The Reachable Matrix Approach for the Shortest Path

作　　者：原慧琳[1,2] 汪定伟[2] 

机构地区：[1]东北大学秦皇岛分校商贸系,河北秦皇岛066004 [2]东北大学信息科学与工程学院,辽宁沈阳110006

出　　处：《信息与控制》2011年第2期202-208,213,共8页Information and Control

基　　金：国家自然科学基金资助项目(70771021);国家自然科学基金创新群体项目(60821063);国家教育部博士点基金资助项目(200801450008)

摘　　要：为了提高传统最短路径算法的效率,文中在细致分析传统算法的基础上,提出了一种在业务流程中计算最短路径及寻找不合理活动环的新方法,此方法被称为最短路径的可达矩阵算法.与原有的最短路径算法相比,该方法将可达矩阵的思想引入到最短路径的计算中,可以在矩阵中显示出活动环及活动路径值.文中还详细描述了该方法所涉及的定义及运算规则.最后,将该方法应用于具体实例,并快速地找到了活动环及活动路径,为业务流程再造提供了一种新的解决方案.Based on careful analysis on the shortest path traditional approaches,a new approach of finding out unreasonable activity loops is present for improving efficiency of the traditional approaches,the approach is named as SPRM（shortest path reachable matrix）.Compared with the previous approaches,SPRM introducs the＂reachable matrix＂into calculating the shortest path and can show activity loops and distances directly.The definition,operating rules of SPRM and others related to SPRM are described.In the end,the approach is applied to a practical process,the loops and paths are found out quickly. The approach provids a new resolution to the business process reengineering（BPR）.

关 键 词：最短路径 可达矩阵 活动环 业务流程重组 

分 类 号：TG335.58[金属学及工艺—金属压力加工]