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

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 🙂

Example of Dijkstra’s Algorithm

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

### Like this:

Like Loading...

*Related*