06_path_reg.png
The MapMaker
User Preferences
Light Pref: "Don't Care"
User Pref: "Bright Spaces"
User Pref: "Dark Spaces"
Dijkstra's Algorithm
  Once I was able to get from A to B, I began to work on including multiple selections in the second iteration of the project. 
  My approach was to use the Dijkstra algorithm from prototype 1 to calculate paths between all possible point of interest (POI) permutations.
  I then looked at each path as a single edge by adding up the length of all the path edges.
  This allowed me to create a subgraph of POIs and their edges, which I could then use to find the best path among all possible paths.
  I needed to find an algorithm to calculate a    Hamiltonian Path    within my subgraph. Unlike Dijkstra, which requires a start and an end point to work, an ideal algorithm for this step would take a start point and find the most optimal route among the remaining nodes, regardless of what node it ends on.     I looked at various approaches to what is essentially a Traveling Salesman Problem, and decided to try the    Nearest Neighbor    algorithm — a    heuristic    approach, which sacrifices some precision to achieve faster results. The Nearest Neighbor traverses the graph, node by node, examining the length of each node's edges, and choosing the shortest among them. 
prev / next