International Journal of Mathematics Trends and Technology
Volume 36 | Number 2 | Year 2016 | Article Id. IJMTT-V36P511 | DOI : https://doi.org/10.14445/22315373/IJMTT-V36P511
Shortest Path problems are among the most studied network flow optimization problems, with interesting applications in a range of fields. Shortest path algorithms are applied automaticallyto find directions between physical locations, such as driving directions on web mapping websites like MapQuest or Google Maps. In a networking or telecommunications mindset, this shortest path problem is sometimes called the mindelay path problem and usually tied with a widest path problem. For example, the algorithm may seek the shortest (min-delay) widest path, or widest shortest (min-delay) path. Many problems can be framed as a form of the shortest path for some suitably substituted notions of addition along a path and taking the minimum. The general approach to these is to consider the two operations to be those of a semiring. Semiring multiplication is done along the path, and the addition is between paths. This general framework is known as the algebraic path problem. Most of the classic shortest-path algorithms (and new ones) can be formulated as solving linear systems over such algebraic structures. Shortest path problems form the foundation of an entire class of optimization problems that can be solved by a technique called column generation. Examples include vehicle routing problem, survivable network design problem, amongst others. In such problems there is a master problem (usually a linear program) in which each column represents a path (think of a path in a vehicle routing problem as one candidate route that a vehicle can take, think of a path in a network design problem as a possible route over which a commodity can be sent between a source and adestination). The master problem is repeatedly solved. Each time, using the metrics of the solution, a separate problem (called the columngeneration sub problem) is solved. This problem turns out to be a shortest path problem (usually with side constraints or negative arc lengths rendering the problem NP-Hard). If a new useful path isobtained, it is added to the original master problem which is now re-solved over a larger subset of paths leading to increasingly better (lower cost, usually)solutions.
[1] C. Xi, F. Qi, and L. Wei, A New Shortest Path Algorithm based on Heuristic Strategy, Proc. of the 6th World Congress on Intelligent Control and Automation, Vol. 1, pp. 2531–2536, 2006.
[2] Dijkstra’s Algorithm Available at http://informatics.mccme.ru/moodle/mod/statements/vie w.php?id=193#1. 2012.
[3] J. Chamero, ―Dijkstra’sAlgorithm Discrete Structures & Algorithms, 2006.
[4] E. W. Dijkstra, A note on two problems in connexion with graphs.NumerischeMathematik 1: 269–271, 1959.
[5] Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM,Volume 5 No 6.
[6] W. K. Chen. Theory of Nets: Flows in Networks. John Wiley &Sons, 1990.
[7] D. Bertsekas and R. Gallager. Data Networks-2nd Edition. Prentice Hall, 1992.
[8] Matthias Hentschel, Daniel Lecking, Bernardo Wagner, Deterministic path planning and navigation for an autonomousforklift truck, Proceedings of IFAC 2007, 2007
[9] Dijkstra’s Algorithm, Available at http://informatics.mccme.ru/moodle/mod/statements/vie w.php?id=193#1. 2012.
[10]J. Chamero, ―Dijkstra’s Algorithm Discrete Structures &Algorithms, 2006.
[11] Kroger, Martin (2005). "Shortest multiple disconnected path for the analysis of entanglements in two- and threedimensional polymeric systems". Computer Physics Communications 168 (168): 209–232. doi:10.1016/j.cpc.2005.01.020.
[12] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin (1993). Network Flows: Theory, Algorithms and Applications. Prentice Hall.ISBN 0-13-617549-X
M. Muthulakshmi, M.M. Shanmugapriya, "Shortest Path Algorithm and its Implementation," International Journal of Mathematics Trends and Technology (IJMTT), vol. 36, no. 2, pp. 82-85, 2016. Crossref, https://doi.org/10.14445/22315373/IJMTT-V36P511
PDF 
Abstract 
Keywords 
References 
Citation