Open Access   Article Go Back

Shortest Route Algorithm Using Dynamic Programming by Forward Recursion

N. Karthikeyan1

Section:Research Paper, Product Type: Journal Paper
Volume-2 , Issue-2 , Page no. 44-48, Feb-2014

Online published on Feb 28, 2014

Copyright © N. Karthikeyan . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

View this paper at   Google Scholar | DPI Digital Library

XML View
PDF Download

How to Cite this Paper

  • IEEE Citation
  • MLA Citation
  • APA Citation
  • BibTex Citation
  • RIS Citation

IEEE Style Citation: N. Karthikeyan, “Shortest Route Algorithm Using Dynamic Programming by Forward Recursion,” International Journal of Computer Sciences and Engineering, Vol.2, Issue.2, pp.44-48, 2014.

MLA Style Citation: N. Karthikeyan "Shortest Route Algorithm Using Dynamic Programming by Forward Recursion." International Journal of Computer Sciences and Engineering 2.2 (2014): 44-48.

APA Style Citation: N. Karthikeyan, (2014). Shortest Route Algorithm Using Dynamic Programming by Forward Recursion. International Journal of Computer Sciences and Engineering, 2(2), 44-48.

BibTex Style Citation:
@article{Karthikeyan_2014,
author = {N. Karthikeyan},
title = {Shortest Route Algorithm Using Dynamic Programming by Forward Recursion},
journal = {International Journal of Computer Sciences and Engineering},
issue_date = {2 2014},
volume = {2},
Issue = {2},
month = {2},
year = {2014},
issn = {2347-2693},
pages = {44-48},
url = {https://www.ijcseonline.org/full_paper_view.php?paper_id=49},
publisher = {IJCSE, Indore, INDIA},
}

RIS Style Citation:
TY - JOUR
UR - https://www.ijcseonline.org/full_paper_view.php?paper_id=49
TI - Shortest Route Algorithm Using Dynamic Programming by Forward Recursion
T2 - International Journal of Computer Sciences and Engineering
AU - N. Karthikeyan
PY - 2014
DA - 2014/02/28
PB - IJCSE, Indore, INDIA
SP - 44-48
IS - 2
VL - 2
SN - 2347-2693
ER -

VIEWS PDF XML
4103 3811 downloads 3919 downloads
  
  
           

Abstract

The current widespread use of location-based services and Global Positioning System technologies has revived interest in very fast and scalable dynamic shortest path queries. We introduce a new shortest path query type in which dynamic constraints may be placed on the allowable set of edges that can appear on a valid forward recursion shortest path. Computing the shortest path between two given locations in a road network is an important problem that finds applications in various map services and commercial navigation products. Our experimental results reveal the characteristics of different techniques, based on which we provide guidelines on selecting appropriate methods for various scenarios. Although the raw data about geography and roads may be more readily available today, computing forward shortest paths is still not trivial. Dynamic algorithm allows us to compute point-to-point dynamic shortest path queries on any road network in essentially linear time. . In a preprocessing stage, these heuristics compute some auxiliary data, such as additional edges (shortcuts) and labels or values associated with vertices or edges.

Key-Words / Index Term

Dynamic Programming, Forward Recursion, Shortest Route, Stage i, State i, Minimum Paths, Backward Recursion

References

[1]. Hamdy A. Taha., Operation Research, Prentice Hall, Eighth Edition, 2011.
[2]. Bertsekas. D., Dynamic Programming: Deterministic and Stochastic Models, Prentice Hall, Upper Saddle River, NJ, 1987.
[3]. Denardo. E., Dynamic Programming theory and Applications, Prentice Hall, Upper Saddle River, NJ, 1982.
[4]. Dreyfus. S and A. Law., The Art and Theory of Dynamic Programming, Academic Press, New York, 1977.
[5]. Sntedovich. M., Dynamic Programming, Marcel Dekker, New York, 1991.
[6]. Taha H. (1997) Operations Research; An introduction, Second Edition Macmillan Publishing Co. inc New York