Optimization of Dijkstra Shortest Path Algorithm

The Objective

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.

This project explored the use of a heuristic in pathfinding to improve performance while possibly sacrificing accuracy.

Science Fair Project done By Ramanan Kandasamy

 

 

<<Back To Topics Page...................................................................................>>Next Topic

Related Projects :

Rubiks Cube Solver using Mathematica
Accurate Simulation of Influenza Pandemics
Self Similar Sierpinski Fractals
Voice Analysis and Recognition
Accuracy in Forestry Management
Frog with the Fear of Water
Correlation between Height and Stride Length

 

 

 

Copyright © www.sciencefairexperiments.org 2012 through 2016

Designed & Developed by Big Brothers