Shortest Path Algorithm for Spatial Query Processing in Road Network

Abstract: If any algorithm has n-shortest path then it has some problem like path similarity among the network expansion and determined path describing turn prohibition. GPS system is an application in the road network field. the meaning of path similarity that is alternative paths derived from k-shortest path algorithm which is connected to lots of links, hence heterogeneity cannot be represented .In road network computing optimal path routes is not easy it�s like a showpiece of real world application algorithm. For computing the optimal route in real road network we can use classic solution from the graph theory which is describe by Dijkstra�s algorithm. But for the large network this is not suitable algorithm. This works too slow for the large road network. This paper proposed link based shortest path algorithm which find out the different path for travelling for node to node network where turn prohibition exist. In this process there is no need of extra node and edge for expanding the network. Dijkstra�s algorithm tested with some example networks then will be expanded to dynamic case.

Keywords: n-shortest path, turn prohibition, wireless network, road network, Routing algorithm, kNN query.