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

XML Persian Abstract Print


Sharif University of Technology
Abstract:   (3790 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]   (1366 Downloads)    
Type of Study: Research | Subject: Special
Received: 2017/06/8 | Accepted: 2017/11/10 | Published: 2018/01/19

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