Shortest Path Star Traversal Using Greedy Search and Dijkstra’s Algorithms

Standard

As part of graph processing algorithm practice, I worked with several teammates to implement the Greedy Search algorithm and an adaptation of Dijkstra’s Algorithm.

The Greedy Search algorithm takes a list of stars positions relative to the Sun (within a 10 parsec radius). After choosing a random starting node, the algorithm visits the closest unvisited star with each iteration. The output produces is the total distance traveled during the traversal of all stars. This algorithm has a runtime around O(n^2).

Greedy Search Example

Greedy Search Example

Secondly, I attempted to modify Dijkstra’s algorithm to minimize the shortest traversed path between all stars within 10 parsecs of the Sun. Dijkstra’s algorithm has a worst case performance of  O(|E|+|V|log|V|). Because |E| represents the number of graph edges and there exists edges between all possible pairs of stars; this algorithm’s total runtime increases very quickly with the addition of more stars. After implementation this algorithm would only complete in a reasonable amount of time by reducing the star count to those within 3 parsecs of the sun 🙂

Dijkstra_Animation

Example of Dijkstra’s Algorithm

Github Repository: https://github.com/MattLamont/Greedy-and-Dijkstra-s-Algorithm-on-HYG-Star-Database.git

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s