Approximating shortest paths in large networks
- UNCW Author/Contributor (non-UNCW co-authors, if there are any, appear on document)
- David Randolph Lorek (Creator)
- Institution
- The University of North Carolina Wilmington (UNCW )
- Web Site: http://library.uncw.edu/
- Advisor
- 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.
Approximating shortest paths in large networks
PDF (Portable Document Format)
459 KB
Created on 1/1/2009
Views: 2592
Additional Information
- Publication
- Thesis
- 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
- Keywords
- Algorithms, Combinatorial optimization, Mathematical optimization, Operations research
- Subjects
- Algorithms
- Combinatorial optimization
- Mathematical optimization
- Operations research