Search for minimal paths in modified networks |
| |
Authors: | Wei-Chang Yeh |
| |
Affiliation: | 1. Department of Mathematics and Mathematical Statistics, Umeå University, SE-901 87 Umeå, Sweden;2. Department of Computing Science, Umeå University, SE-901 87 Umeå, Sweden |
| |
Abstract: | The problem of searching for all minimal paths (MPs) in a network obtained by modifying the original network, e.g. for network expansion or reinforcement, is discussed and solved in this study. The existing best-known method to solve this problem was a straightforward approach. It needed extensive comparison and verification, and failed to solve some special but important cases. Therefore, a more efficient, intuitive and generalized method to search for all MPs without an extensive research procedure is proposed. In this presentation, first we develop an intuitive algorithm based upon the reformation of all MPs in the original network to search for all MPs in a modified network. Next, the computational complexity of the proposed algorithm is analyzed and compared with the existing methods. Finally, examples illustrate how all MPs are generated in a modified network based upon the reformation of all of the MPs in the corresponding original network. |
| |
Keywords: | Reliability Modified network Shortest path Minimal paths |
本文献已被 ScienceDirect 等数据库收录! |
|