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).
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 🙂