Finding the Shortest Route in San Francisco
My CS225 final project where my team and I designed a searching DFS algorithm to find the shortest path between two nodes in our San Francisco road network data.
Developed in CS225 as our final project with zixuanw8, maxjm2, and arliang2. The goals of our project are as follows:
Can DFS be Used to Traverse a Map?
Searching larger undirected maps can be resource intensive if not done efficiently. Smaller maps can be traversed using recursion; specifically, when traversing with DFS, one can traverse all the way down a branch before recursively calling another traversal down another branch. Since our dataset has over 30,000 nodes, recursively calling traversals will overflow the call stack. Therefore, we decided to use a dedicated stack to store the traversal queue, which saved us space on the call stack.>
Implementing Dijkstra's Algorithm to Find the Shortest Path
To implement Dijkstra's Algorithm, we created an adjacency list which held pointers to each adjacent node. From there, we created a priority list using a self-balancing BST to find the shortest path from between two adjacent nodes.
Implementing a Slope Check Algorithm for a Visual PNG Representation
To print a visual depiction of the generated graph, and the shortest path between to nodes, we implemented a slope checking algorithm. Depending on the direction from one node to it’s adjacent node, we traverse one of four possible directions: up, down, left, or right. For example, if the adjacent node is up and to the left of the starting node, we either color the pixel above the starting node, or the pixel to the right of the starting node. We check the slopes of each possible traversal, and traverse to the pixel with the slope that's closest to the slope of the starting and ending node. We then color the pixel traversed, and repeat the same process till we reach the ending node.