The Cycled Shortest Path Problem: A New Perspective, And Sensitivity Analysis
Asghar Aini *
Department of Industrial Engineering, Sharif University of Technology, Azadi Avenue, 14598, Tehran, Iran.
Kourosh Eshghi
Department of Industrial Engineering, Sharif University of Technology, Azadi Avenue, 14598, Tehran, Iran.
Amir Salehipour
CARMA, The University of Newcastle NSW 2308, Australia.
*Author to whom correspondence should be addressed.
Abstract
Several algorithms, including the Floyd-Warshall algorithm, have been developed to calculate the shortest path between every pair of vertices in a graph (network) with cycles. This study proposes an exact algorithm, the Cascade Rectangle (CR) algorithm, for calculating the shortest paths between every pair of vertices in cycled graphs. The algorithm is developed by designing and implementing certain improvements to the available exact algorithms. In particular, the proposed algorithm has an improved computational complexity, although its worst computational complexity is O(n3). Moreover, the CR algorithm is easier to implement, which is an advantage for teaching and learning purposes. In addition to this, we introduce a new concept, the transposition matrix, which has important applications in sensitivity analysis and re-optimization of the shortest path networks. An example illustrates the CR algorithm and the new concept of transposition matrix.
Keywords: The cycled shortest path problem, cascade rectangle algorithm, transposition matrix, sensitivity analysis, shortest path network re-optimization