International Journal of Scientific & Technology Research

Home About Us Scope Editorial Board Contact Us

IJSTR >> Volume 5 - Issue 9, September 2016 Edition

International Journal of Scientific & Technology Research  
International Journal of Scientific & Technology Research

Website: http://www.ijstr.org

ISSN 2277-8616

Establishment Of The Shortest Route – A Prototype For Facilitation In Road Network

[Full Text]



Sumaira Yousuf Khan, Nasir uddin Khan, Mushtaq Hussain, Farhan Mazhar, Abdul Mannan



Dijkstra’s Algorithm (DA), Shortest Route, Optimal path, Network Design



Calculating the shortest path between two locations in a road network is a significant problem in network analysis. Roads play a pivotal role in day to day activities of masses live in places and areas. They travel for various purposes that are, to study, to work, to shop and to supply their goods and the like, from one place to another place. Even in this modern era, roads remain one of the mediums used most frequently for travel and transportation. Being ignorant of the shortest routes people sometimes have to travel long distances, consume extra precious time, money and bare undesirable mental stress. Karachi is the second most populated and the seventh biggest city of the world. It is the central place of Pakistan, which is famous for industry, banking, trade and economic activity, and there are places which frequently visit by the inhabitants for their miscellaneous requirements. Federal Board of Revenue (FBR) is one of the departments that deal with taxation and revenue generation in the country. A common man residing near or distant areas often visit FBR to settle their business / property and tax related issues. In order to facilitate the masses, an effort is being made to develop a prototype based on Dijkstra’s Algorithm (DA) to establish a shortest route, that will help individuals in navigation and subsequently alleviate difficulties faced by them in travelling/ road networks.



[1] Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1988). Network flows (No. MIT-WP-2059-88). ALFRED P SLOAN SCHOOL OF MANAGEMENT CAMBRIDGE MA.

[2] Glover, F., Klingman, D., & Phillips, N. V. (1992). Network models in optimization and their applications in practice (Vol. 36). John Wiley & Sons.

[3] Zhang, F., Qiu, A., & Li, Q. (2005). Improve on Dijkstra shortest path algorithm for huge data. Chinese academy of surveying and mapping: China.

[4] Jahan, S., & Hasan, M. S. (2011). A comparative study on algorithms for shortest-route problems and some extensions. International Journal of Basic and Applied Sciences IJBAS-IJENS, 11, 167-177.

[5] Dijkstra, E. W. (1959). A note on two problems in connexion with graphs.Numerische mathematik, 1(1), 269-271.

[6] https://en.wikipedia.org/wiki/Federal_Board_of_Revenue_(Pakistan)

[7] Magzhan, K., & Jani, H. M. (2013). A review and evaluations of shortest path algorithms. International journal of scientific & technology research,2(6).

[8] Taha, H. A. (1982). Operations Research: An Introduction (For VTU). Pearson Education India, p 219-222

[9] Gogoncea, V., Murariu, G., & Georgescu, L. (2010). The Use of Dijkstra's Algorithm in Waste Management Problem. Annals of Dunarea de Jos University of Galati, Mathematics, Physics Theoretical Mechanics, 196-200.

[10] Xiao-Yan, L., & Yan-Li, C. (2010, August). Application of Dijkstra Algorithm in Logistics Distribution Lines. In Third International Symposium on Computer Science and Computational Technology (ISCSCT’10), Jiaozuo, PR China (pp. 048-050).

[11] Balstrřm, T. (2000). Identifying least cost routes in mountainous terrain. In2000 Esri User Conference Proc.(cd-rom Titel). ESRI.

[12] https://www.google.com/maps/@37.0625,-95.677068,4z

[13] Dreyfus, S. E. (1969). An appraisal of some shortest-path algorithms.Operations research, 17(3), 395-412.

[14] Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1996). Shortest paths algorithms: Theory and experimental evaluation. Mathematical programming, 73(2), 129-174.