Tawanda’s non- iterative optimal tree algorithm for shortest route problems

Authors

  • Trust Tawanda Department of Applied Mathematics-Operations Research and Statistics, National University of Science and Technology, PO Box AC 939, Ascot, Bulawayo, Zimbabwe

Keywords:

Shortest route problem, Algorithm, Road networks

Abstract

So many algorithms have been proposed to solve the shortest path in road networks, in this paper, an algorithm is developed to solve shortest route problems. The algorithm is being demonstrated through solving of various network problems. The principle of the algorithm consist in  transforming  the graph into a tree by means of arc and node replication, thereby expanding outwards from the source node  considering all possible paths up to the destination node. The objective is to develop a method that can be applied in directed and non-directed graphs.

References

Anderson Dr, Sweeney Dj & Williams Ta (2000) Quantitative methods for business, south-west college publishing.

Cherkassy B V, Goldberg A V and Radzik T. (1993) Shortest Paths Algorithms:Theory and Experimental Evaluation. Research project, Department of Computer Science, Cornell and Stanford Universities and Krasikova Institute for Economics

and Mathematics.

Dijkstra EW (1959). A Note on Two Problems in Connection with Graphs. Numer. Math. 1:269-271

Ellias Horowitz and Sartaj Sahni (1990) Fundamentals of data structures in pascal, freeman and company, New York, 3rd edition.

Faramroze, Fast shortest path Algorithm for large road network.

Goldberg Av, Silverstein C (1997). Implementations of Dijkstra’s Algorithms Based on Multi-Level Buckets. In: Pardalos PM, Hearn DW, Hages WW (eds) Lecture Notes in Economics and Mathematical Systems, 450:292-327.

Gallo G, Pallottino S (1988). Shortest Path Algorithms. Ann. Oper. Res. 13:3-79.

Gallo G, Pallottino S (1982). A New Algorithm to Find the Shortest Paths between All Pairs of Nodes. Discrete Appl. Math. 4:23-35.

Hillier FS, Lieberman GJ (2001). Introduction to Operations Research, 7th Edition. MacGraw-Hill, New York.

Hamdy A Taha (2007) 8th EDITION, Operations research: An introduction, Pearson prentice hall, Inc.

Hao-Yu W, Li-Shun L, Xiao-Juan J, Zong-Kuan W (2011). Shortest Path Optimisation in Intelligent Transportation System. Energy Procedia 13:3589-3593.

Ji X, Iwamura K, Shao Z (2007). New Models for Shortest Path Problems with Fuzzy Arc Lengths. Appl. Math. Modeling 31:259-269.

Ke Deng and Xiaofang Zhou, "Expansion-Based Algorithms for Finding Single Pair Shortest Path on Surface", in Proceedings of the 4th International Workshop on Web and Wireless Geographical Information Systems, (LNCS 3428), pages 151-163, Springer, November 2004, Seoul, Korea (Rank C by ERA).

Markland RE, Sweigart JR (1987). Quantitative Methods: Applications to Management Decision Making, 3rd Edition. John Wiley & Sons, New York.

Winston LW (2004). Operations Research: Applications and Algorithms, 4th Edition. Thomson Brooks/Cole, International.

Downloads

Published

2013-02-28

How to Cite

Tawanda, T. . (2013). Tawanda’s non- iterative optimal tree algorithm for shortest route problems. Scientific Journal of Pure and Applied Sciences, 2(2), 87-94. Retrieved from http://sjournals.com/index.php/sjpas/article/view/1004

Issue

Vol. 2 No. 2 (2013): February

Section

Mathematics

License

Copyright (c) 2013 Trust Tawanda

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.