The Cycled Shortest Path Problem: A New Perspective, And Sensitivity Analysis
Asghar Aini, Kourosh Eshghi, Amir Salehipour
Journal of Advances in Mathematics and Computer Science · pp. 1–14 · Published 22 Aug 2017
10.9734/JAMCS/2017/34933Abstract
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.
Cited by 0
No indexed citations yet.
Related research
- Optimum Allocation of Water and Land Resource for Maximizing Farm Income of Jabalpur District, Madhya Pradesh — shares topic coverage
- Assessment of Projected Climate Change Impact on Green Gram Productivity through DSSAT Model under South Gujarat Environmental Condition — shares topic coverage
- Deterministic Mathematical Model for Dynamics of Water Borne Diseases — shares topic coverage
- Mathematical Analysis of Plant Disease Dispersion Model that Incorporates wind Strength and Insect Vector at Equilibrium — shares topic coverage
- Simulation Studies on Recovery of Acetonitrile from Aqueous Acetonitrile Waste from Pharmaceutical Processes — shares topic coverage
Article metrics
Real usage data collected on this platform.
0
Page views
0
PDF downloads
0
Outbound clicks
0
Citations
Views by country
Approximate, from request IP at view time — not citizenship or institution. Countries with fewer than 5 views are grouped as "Other".
No views recorded yet.
Traffic sources
Referring site, by host.
No traffic recorded yet.
Views and downloads exclude known bots/crawlers. Citations combines this platform's own DOI-resolved index with each external source's own reported total — see Cited by above for individually listed citing works. Last refreshed 0 seconds ago.