Abstract:
Nowadays, people widespread use of
smartphones and ubiquitous devices for map based services.
As the transport network is complicated and massive, people
may be confused to reach the desired location after finding a
location. Many searching techniques are used for finding the
shortest path, might still not be fast enough in certain realtime applications because of complexing transport network.
Search time can be reduced if we pruned unnecessary clusters
in a complex large graph. Memory utilization is safe for the
processing time if we reduce search space in complex network.
For removing unnecessary clusters, adjacency matrices,
distance based methods and K-means clustering can be used.
ArcGIS software and popular shortest path algorithms are
applied to find the shortest path from one location to another
on the Android mobile platform. In addition, the performance
of finding the shortest path using popular A* and Dijkstra
algorithms with bidirectional search can be compared before
and after removing unnecessary clusters.
