Approximating shortest paths in large networks

UNCW Author/Contributor (non-UNCW co-authors, if there are any, appear on document)
David Randolph Lorek (Creator)
The University of North Carolina Wilmington (UNCW )
Web Site:
Yaw Chang

Abstract: 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.

Additional Information

A Thesis Submitted to the University of North Carolina Wilmington in Partial Fulfillment Of the Requirements for the Degree of Master of Science
Language: English
Date: 2009
Algorithms, Combinatorial optimization, Mathematical optimization, Operations research
Combinatorial optimization
Mathematical optimization
Operations research

Email this document to