A new algorithm in enumerating all minimal paths in a sparse network

被引：60

作者：

Kobayashi, K

Yamamoto, H

机构：

[1] Res Inst Syst Planning, Shibuya Ku, Tokyo 1500031, Japan

[2] Tokyo Metropolitan Inst Technol, Dept Prod Informat Syst, Hino, Tokyo 1910065, Japan

来源：

RELIABILITY ENGINEERING & SYSTEM SAFETY | 1999年 / 65卷 / 01期

关键词：

minimal paths; depth-first-search; reliability; sparse network; enumeration;

D O I：

10.1016/S0951-8320(98)00076-3

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

In this paper an efficient algorithm is proposed that generates all minimal paths in a sparse network. When we analyze a complex network reliability, it is important to enumerate all minimal paths. The DFS algorithm is the well-known method for enumerating all minimal paths. Shen has provided a DFS algorithm that is simple and easy to program. Our proposed algorithm is composed of Shen's algorithm and some additional processes. Computational results show that our algorithm is more efficient than Shen's for many sparse networks. (C) 1999 Elsevier Science Ltd. All rights reserved.

引用

页码：11 / 15

页数：5