The Cycled Shortest Path Problem: A New Perspective, And Sensitivity Analysis
Journal Title: Journal of Advances in Mathematics and Computer Science - Year 2017, Vol 24, Issue 1
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.
Authors and Affiliations
Asghar Aini, Kourosh Eshghi, Amir Salehipour
Keywords
Related Articles
- EP ID EP321912
- DOI 10.9734/JAMCS/2017/34933
- Views 89
- Downloads 0
Solution of Wind Speed Equation of Circulation Cyclone and Its Application
The wind speed equation of circular cyclone is a set of non-linear partial differential equations (PDE) with 4 unknown functions u (wind speed), ρ (density), p (pressure) and T (temperature) and is separated to 14 unknow...
Comparison among Unstructured TVD, ENO and UNO Schemes in Two-dimensions
In this work, unstructured TVD, ENO and UNO schemes are applied to solve the Euler equations in two-dimensions. They are implemented on a finite volume context and cell centered data base. The algorithms of Yee, Warming...
A Design of a Low-Reynolds Number Airfoil that Leads to the Formation of Separation Bubbles at the Leading Edge
The aerodynamics of airfoils at low Reynolds numbers (Re) has become increasingly important from both fundamental and industrial points of view, due to recent developments in small wind turbines, small-unmanned aerial ve...
Estimation in Step-stress Partially Accelerated Life Test for Exponentiated Pareto Distribution under Progressive Censoring with Random Removal
Accelerated life testing or partially accelerated life testing is generally used in manufacturing industries since it affords significant minimization in the cost and test time. In this paper, a step-stress partially acc...
Time Series Analysis for Modeling and Forecasting International Tourist Arrivals in Sri Lanka
Tourism is one of the income generating industries in a developing country which directly contribute to the economy. Therefore, forecasting tourist arrivals is important for making policy decisions to improve facilities...