Finding the Shortest Path between the Parking Lots in a Park with Graph Theory

1. Introduction

This is a math project I did in high school. My aim was to use the knowledge of graph theory to find the shortest path (along the walking trails) between the two parking lots in Point Pleasant Park (a small park in Eastern Canada). Graph theory is just as fascinating now as it was when I did this, above all because of its obvious real-world applications. Probably the most insightful part of this project is when I explain why Dijkstra’s algorithm works, under “Iteration 2”.

2. Exploring Basic Graph Theory

Graphs
Informally, a graph can simply be thought of as a structure of points connected to each other by lines. An example to clarify:
1
Figure 1. An example of a graph.
This shows a graph, with four ‘points’ (A, B, C, D) connected to one another by ‘lines’ (AB, AC, AD, CD). In graph theory terminology, these points are referred to as vertices, and the lines that connect them are called edges. Two vertices are called adjacent if they are connected directly by an edge (Caldwell, 1995); for instance, A and B in the above graph are adjacent, for they are connected by edge AB.

Due to their focus on connections, graphs are often used to represent and study connections between real-life objects. For instance, graphs are used to study the connections in transportation networks. Here, the graph’s vertices represent places of interest (e.g., towns or cities) and its edges represents links – such as roads or railways – between these places (Marr, n.d.).

Paths
A path is simply a ‘journey’ around a graph, where one travels from vertex to vertex. For example, consider a journey around the graph above, where someone starts at A, then goes to D (by traveling along edge AD), and then goes to C (along edge CD). This is path ADC. Also, in a path, no edge can be traveled along, and no vertex can be visited, more than once.

Weighted Graphs
A special kind of graph, known as weighted graphs, have numbers (called weights) associated with each edge. Weights can represent a cost to travel along an edge, or a distance. As an example of a weight, in the weighted graph shown below, edge AB has a weight of 5.
2
Figure 2. An example of a weighted graph.
The weight of a path on a weighted graph equals the sum of the weights of the edges travelled along in the path (Zhang, n.d.). For example, the weight of path ADC in the above graph is 6 + 2 = 8 (i.e., the sum of the weights of edges AD and CD).

3. Application: Modeling Point Pleasant Park as a Graph

Now that we know what graphs and paths are, we can now model Point Pleasant Park as a graph, to help us in finding the shortest path (distance-wise), along the walking trails, between the two parking lots. Google Maps (2014) shows Point Pleasant Park and its trails below. Two red points have been added to show the starting parking lot (A) and the destination parking lot (Z).
3
Figure 3. A map of Point Pleasant Park, with starting and ending positions marked.
One may notice I cut off some of the map at the bottom. I deliberately did so because the trails in the lower end of the park would obviously not be a part of the shortest path between the parking lots, which are in the upper end.

Once I finished preparing the map, I was initially confused about how to make a graph out of it. I was unsure of what the vertices should be. Ultimately I realized I could make each intersection a vertex. I started by making a vertex wherever two (or more) trails met. I then deleted any ‘insignificant’ vertices, such as a vertex where multiple trails met but only one of the trails could be a part of the shortest path. For example:
4
Figure 4. An example of an insignificant vertex, D.
In this case, I deleted vertex D because, although there is an intersection, only one of the trails, Cambridge Drive, could be part of the shortest path – the other leads away from the destination! This makes it easier to solve the problem, by making the graph simpler and nicer to work with.

After the vertices, I added edges. I connected the vertices using edges in the same way that the intersections (that the vertices represent on the map) were connected by segments of trails. In other words, each edge represents a segment of trail that is between two intersections. Trails leading to dead-ends, or away from the destination, were not added as edges. For instance:
5
Figure 5. A part of the map (left) modelled as a graph (right). As one can see, certain trails were not included.
After making the first version of the graph, I added weights. Each weight represents the length (in meters) of each stretch of trail that was represented by an edge. I obtained these values using Google Maps’ Directions feature. I then simplified further. I looked at any two vertices which had two edges connecting them, and deleted the edge with greater weight. For example, in the instance below, I deleted the edge with weight 130 because it is obvious that this could never be a part of the shortest path – you would always select the edge with weight 83 instead.
6
Figure 6. The edge with weight 130 is extraneous and so deleted.
Finally, I deleted all vertices whose sole purpose was to ‘connect’ exactly two edges. For example, vertex G in figure 5 can be deleted. The two edges BG and GH are consolidated into one edge BH whose weight equals the sum of the weights of BG and GH. This unfortunately makes the graph look less like the map, but reducing the number of vertices does make the problem easier to solve. Doing this gave me the final version of the graph:

7
Figure 7. The relevant section of Point Pleasant Park, modelled as a graph.

4. Finding the Shortest Path: Dijkstra’s Algorithm

With the basic knowledge of graph theory, and the graph of Point Pleasant Park, we can learn about Dijkstra’s algorithm and then find the shortest path between the parking lots.

The Purpose of Dijkstra’s Algorithm
Dijkstra’s algorithm lets us solve the shortest path problem. That is, it basically finds the path of minimum weight between two vertices in a weighted graph. The shortest path problem can be solved for very small graphs by finding all paths between the two vertices, but for larger graphs where there are many paths between two vertices, this method would be very inefficient. Dijkstra’s algorithm provides a more systematic way of solving the shortest path problem.

Other Algorithms
Dijkstra’s algorithm is not the only algorithm that can solve the shortest path problem. Another popular algorithm is the Bellman-Ford algorithm. Both have advantages and disadvantages. Dijkstra’s algorithm is simpler and faster, but the Bellman-Ford algorithm can work with negative-weight edges, unlike Dijkstra’s algorithm (MIT OpenCourseWare, 2013). Sometimes negative-edge weights are applicable (e.g., if weights represent monetary costs, a negative weight may represent a gain of money). However, in our park model, all weights are positive (our weights represent distances, which must be positive), so, Dijkstra’s algorithm was chosen.

The Basic Idea of Dijkstra’s Algorithm
Dijkstra’s algorithm involves labeling and boxing vertices around a graph. A vertex that is labeled has been labeled with the weight of some path (not necessarily the shortest) between it and the starting vertex. But once we have determined that this path is in fact the shortest path between the labeled vertex and the starting vertex, we draw a box around the vertex and its label. Therefore, once we box the destination vertex, the algorithm is effectively over.

The Procedure of Dijkstra’s Algorithm
Label the starting vertex with ‘0’ and box it. Then repeat the following two steps until the destination vertex has been boxed. Each repetition of the steps is called an iteration.

Step 1. Consider all the unboxed vertices adjacent to the vertex which has most recently been boxed. Some of these adjacent vertices may already have labels; some may not. Nonetheless, there is a ‘potential label’ for each. The ‘potential label’ equals the weight of the shortest path between the starting vertex and the latest boxed vertex (i.e., the boxed vertex’s label) plus the weight of the edge between the latest boxed vertex and the adjacent vertex being considered.

Step 2. After completing the first step, identify the labeled and unboxed vertex with the smallest label, and box it. Because this vertex (call it Q) has the smallest unboxed label, it means that we know the weight of the shortest path between the starting vertex and Q – this weight is Q’s label. Now repeat the first step, considering the vertices adjacent to Q.
Dijkstra’s algorithm only discovers the weight of the shortest path to each boxed vertex. But, we can easily discover the shortest path itself by ‘backtracking’. To help do this, when we add/update a vertex’s label, we mark on the label which boxed vertex the label came from.

Example Problem
A fairly simple example will consolidate our knowledge of Dijkstra’s algorithm. For the graph below, we will try to find the shortest path between vertices A and D using Dijkstra’s algorithm.
8
Figure 8. A weighted graph to which Dijkstra’s algorithm will be applied.
The starting vertex, A, has already been labeled with 0 and boxed. We may now begin completing iterations of the steps until we box vertex D, the destination vertex.

Iteration 1. Consider B and C, the unboxed vertices adjacent to the most recently boxed vertex, A. Because they have no labels, we will assign to both their potential label. The label of B equals label of A + weight of edge AB = 0 + 7 = 7. Using the same process, the label of C is 10. We then move onto step 2: identify the unboxed vertex with the smallest label and box it. This is vertex B. We note on each vertex’s label which boxed vertex the label came from (vertex A).
9
Figure 9. The result of Iteration 1.
Iteration 2. Consider C, D, and E, the unboxed vertices adjacent to B, the most recently boxed vertex. The potential label for C = 7 + 6 = 13. Likewise, the potential labels for D and E are calculated to be 19 and 11, respectively. As 13 is greater than 10, the label of C remains the same. But the other vertices are assigned their potential labels, since they do not yet have labels. For step 2, C is boxed, as it has the smallest unboxed label. Recall that Dijkstra’s algorithm claims that, for the vertex with the smallest unboxed label, its label equals the weight of the shortest path between it and the starting vertex (here, the weight/label is 10). Let us now consider why this claim is true, and, thus, why Dijkstra’s algorithm works. We know that path AC is the shortest path between A and C which consists only of boxed vertices, because in step 1 we consider the paths which only consist of boxed vertices (in this case, AC and ABC), and choose the shortest one (when we let C’s label remain the same, we were choosing AC as the shortest path). But how do we know that there is not a shorter path, which goes through an unboxed vertex, such as E? We know because their labels are larger than C’s (we boxed C because it has the smallest label), i.e., the paths from A to the unboxed vertices are longer than path AC. And since there are no negative-weight edges (Dijkstra’s algorithm stipulates this), there is no way for these paths to decrease their weight before reaching C. Therefore, we have shown there is no path between A and C shorter than AC, and we have explained why the claim is true.
10
Figure 10. The result of Iteration 2.
Iteration 3. Continuing the steps, D and E (the unboxed vertices adjacent to C) have potential labels calculated: 15 for D, and 14 for E. Because 15 is less than 19 (the current label of D), D has its current label replaced by its potential label. However, because 14 is greater than 11, the label of E remains the same. Vertex E has the smallest unboxed label and is thus boxed.
11
Figure 11. The result of Iteration 3.
Iteration 4. Continuing the steps, D has its label changed to 13 (its potential label from E). It is the smallest unboxed label, so it is boxed.
12
Figure 12. The result of Iteration 4.
The destination vertex has been boxed, so the algorithm is complete. We are not technically finished, as we have not actually determined the shortest path. This can be done by backtracking. We already know the last vertex in the shortest path (it is the destination vertex, D). To find the second-last vertex in the path, look at the vertex which is on the label of D – this is E. To find the third-last vertex, look at the vertex which is on the label of the second-last vertex, E. This is B. Then look at the vertex on B’s label; this is A. A is the starting vertex, so we are done. The shortest path between A and D in the example is determined to be ABED.

5. Application: Solving the Shortest Path Problem with Dijkstra’s Algorithm

We are now in a position to apply Dijkstra’s algorithm to our graph of Point Pleasant Park (see figure 7) in order to solve our shortest path problem. Remember, the goal is to find the shortest path between the two parking lots (vertices A and Z).
Because it would be impractical to show a diagram for each iteration of Dijkstra’s algorithm, I will simply represent the results of the algorithm as a table.
figgie
Figure 13. Results of Dijkstra’s algorithm applied to the Point Pleasant Park graph.
Once the destination vertex (Z) is boxed, the algorithm is over. We have determined that the shortest path from A to Z has weight 963, meaning that the shortest path between the two parking lots is 963m long. But we want to find the shortest path itself. Applying the process of backtracking described above, the shortest path is found to be ABCDIKLMWZ. In terms of the actual park trails, the path is:

14
Figure 14. The shortest path between the two parking lots.

References

Caldwell, C. (1995). Graph theory glossary. Retrieved from http://www.utm.edu/departments/math…

Google Maps. (2014). [Point Pleasant Park, Halifax, Nova Scotia] [Street map]. Retrieved from https://www.google.com/maps/@44.622…

Marr, P. (n.d.). Transportation systems as networks [PDF document]. Retrieved from http://webspace.ship.edu/pgmarr/Tra…

MIT OpenCourseWare. (2013, January 14). Single-source shortest paths problem [Video file]. Retrieved from https://www.youtube.com/watch?v=Aa2…

Zhang, H. (n.d.). Weighted graph algorithms [PDF document]. Retrieved from http://homepage.cs.uiowa.edu/~hzhan…
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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s