Approximating shortest paths in large networks
David Randolph Lorek · NC Digital Online Collection of Knowledge and Scholarship (The University of North Carolina at Greensboro) · 2009
In the classroom students are introduced to shortest route calculation using small datasets (those that can be hand-drawn.) For demonstrating the application of an algorithm a small dataset is typically sufficient. However, real-world applications of shortest path calculations seem to be useful only when applied to large datasets. This paper presents research on a computer based implementation of a modified Dijkstra algorithm as applied to large datasets including tens of thousands of arcs. In an attempt to improve the performance of calculating paths two heuristics are also examined. The intuition behind the heuristics is to remove the arcs that will likely not be traversed by the optimal path from the set of arcs that can possibly be traversed by the optimal path. By reducing this number less labeling is required, resulting in fewer CPU cycles being used to generate a route. This paper compares the results of the optimal against those of the two heuristics.