An Optimization of Dijkstra's Shortest Path Algorithm

Overview

Objectives/Goals The goal of this project was to optimize path finding around polygonal obstacles in 2-dimensional euclidean space. An increase in performance was achieved by allowing for imperfect paths, but the question was whether the performance increase was enough to justify the loss in accuracy. Methods/Materials The objective was achieved by first converting 2-dimensional maps into abstract node graphs, while preserving data on geometric location. Dijkstra's algorithm was then used on the node graph, but modified to run faster using this extra data. However this optimization changes Dijkstra's Algorithm so that it only finds a path, rather than the shortest path. Results It was found that although factoring in this optimization to larger degrees did lead to significant imperfections, a balanced level was located where not only were perfect or near-perfect paths were found, but they were also found in the shortest time. Conclusions/Discussion While this project focused on a particular problem, the approach can be applied to many other computing applications. Perfect solutions are not always necessary, and by allowing a small error vast increases in performance can be achieved. This is already demonstrated in lossy compression of media, but it can and should be explored further.

Competition history

• CSEF 2008 Mathematics & Software · Entry S1311

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2008 project