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 88
- Downloads 0
Analytical Modeling of the Thermoelectric Effect in Photovoltaic Cells: Combined Solar Photovoltaic and Thermoelectric Generator System (PV+TEG)
Aims: Analytical modeling of the combined systems photovoltaic-thermoelectric (PV + TEG). The advantage of these systems is double: On the one hand, they allow to cool the photovoltaic cells (PV), which avoids the loss...
Mathematical Model of Drinking Epidemic
A non-linear SHTR mathematical model was used to study the dynamics of drinking epidemic. We discussed the existence and stability of the drinking-free and endemic equilibria. The drinking-free equilibrium was locally as...
Optimal Control Model of Malaria Disease with Standard Incidence Rate
In this research article, an optimal control model of malaria disease with standard incidence rate is proposed. Maximum Principle was employed to derive the necessary conditions for the existence of optimal control. Nume...
Extensions of Locally Compact Abelian, Torsion-Free Groups by Compact Torsion Abelian Groups
Let X be a compact torsion abelian group. In this paper, we show that an extension of Fp by X splits where Fp is the p-adic number group and p a prime number. Also, we show that an extension of a torsion-free, non-divisi...
Estimated Numerical Results and Simulation of the Plant Disease Model Incorporating Wind Strength and Insect Vector at Equilibrium
Numerical simulations facilitate in the study of the behaviour of systems whose mathematical models are too complex to obtain analytical solutions. In this paper, we used assumed values of the model parameters and variab...