Volume 14, Issue 4 (12-2017)                   jor 2017, 14(4): 67-87 | Back to browse issues page

XML Persian Abstract Print

Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Aini A, Eshghi K. Cascade rectangle algorithm and transposition matrix in the cycled shortest path networks.. jor. 2017; 14 (4) :67-87
URL: http://jamlu.liau.ac.ir/article-1-1318-en.html
Sharif University of Technology
Abstract:   (2999 Views)

Shortest path problem is among the most interesting problems in the field of graph and network theory. There are many efficient matrix based algorithms for detecting of shortest path and distance between all pairs of this problem in literature. In this paper, a new exact algorithm, named Cascade Rectangle Algorithm, is presented by using main structure of previous exact algorithms and developing some new techniques. In cascade rectangle algorithm, all mathematical calculations  and  operations execute in multi rectangle structure. This algorithm is an efficient exact algorithm with simple procedure and fast running time. Furthermore, a new matrix on the basis of route matrix, called Transposition Matrix, is defined to apply the sensitivity analysis and reoptimization of the all pairs shortest path networks. Finally, one illustrative example is also solved to show the details of cascade rectangle algorithm, floyd-warshall algorithm, revised matrix algorithm and Transposition Matrix  step by step.

Full-Text [PDF 935 kb]   (967 Downloads)    
Type of Study: Research | Subject: Special
Received: 2017/06/8 | Accepted: 2017/11/10 | Published: 2018/01/19

Add your comments about this article : Your username or Email:

Send email to the article author

Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.