The Cycled Shortest Path Problem: A New Perspective, And Sensitivity Analysis

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.