Graph Theory Basics: Learn It 2

Lumen Learning

Graph Theory Basics: Learn It 2

Shortest Path

When you use Google Maps to ask for directions from your home to your Aunt’s house, you are usually looking for the shortest path between the two locations. Computer applications use representations of the street maps as graphs, with estimated driving times as edge weights.

While often it is possible to find the shortest path on a small graph by guess-and-check, our goal in this section is to develop methods to solve complex problems in a systematic way by following algorithms. An algorithm is a step-by-step procedure for solving a problem. Dijkstra’s (pronounced dike-stra) algorithm will find the shortest path between two vertices.

Dijkstra’s Algorithm

Mark the ending vertex with a distance of zero. Designate this vertex as current.
Find all vertices leading to the current vertex. Calculate their distances to the end. Since we already know the distance the current vertex is from the end, this will just require adding the most recent edge. Don’t record this distance if it is longer than a previously recorded distance.
Mark the current vertex as visited. We will never look at this vertex again.
Mark the vertex with the smallest distance as current, and repeat from step [latex]2[/latex].

Suppose you need to travel from Tacoma, WA (vertex [latex]T[/latex]) to Yakima, WA (vertex [latex]Y[/latex]). Looking at a map, it looks like driving through Auburn ([latex]A[/latex]) then Mount Rainier ([latex]MR[/latex]) might be shortest, but it’s not totally clear since that road is probably slower than taking the major highway through North Bend ([latex]NB[/latex]). A graph with travel times in minutes is shown below. An alternate route through Eatonville ([latex]E[/latex]) and Packwood ([latex]P[/latex]) is also shown.

Graph with 7 vertices marked T, A, NB, Y, MR, P, and E. The length between NB and Y is labeled 104, between NB and A is 36, between A and T is 20. Between T and E is labeled 57, and between E and P is 96. Length between P and Y is labeled 76. Between P and MR is labeled 27, and between MR and A is 79.

Step [latex]1[/latex]: Mark the ending vertex with a distance of zero. The distances will be recorded in [brackets] after the vertex name.

Step [latex]2[/latex]: For each vertex leading to [latex]Y[/latex], we calculate the distance to the end. For example, [latex]NB[/latex] is a distance of [latex]104[/latex] from the end, and [latex]MR[/latex] is [latex]96[/latex] from the end. Remember that distances in this case refer to the travel time in minutes.

Graph with 7 vertices marked T, A, NB, Y, MR, P, and E. teh length between NB adn Y is labeled 104, between NB and A is 36, between A and T is 20. Between T and E is labeled 57, and between E and P is 96. Length between P and Y is labeled 76. Between P and MR is labeled 27, and between MR and A is 79. Additionally, Y is labeled with [0], NB is labeled with [104], MR is labeled with [96], and P is labeled with [76].

Step [latex]3[/latex] & [latex]4[/latex]: We mark [latex]Y[/latex] as visited, and mark the vertex with the smallest recorded distance as current. At this point, [latex]P[/latex] will be designated current. Back to step [latex]2[/latex].Step [latex]2[/latex] (#[latex]2[/latex]): For each vertex leading to [latex]P[/latex] (and not leading to a visited vertex) we find the distance from the end. Since [latex]E[/latex] is [latex]96[/latex] minutes from [latex]P[/latex], and we’ve already calculated [latex]P[/latex] is [latex]76[/latex] minutes from [latex]Y[/latex], we can compute that [latex]E[/latex] is [latex]96+76 = 172[/latex] minutes from [latex]Y[/latex].

Step [latex]3[/latex] & [latex]4[/latex] (#[latex]2[/latex]): We mark [latex]P[/latex] as visited, and designate the vertex with the smallest recorded distance as current: [latex]MR[/latex]. Back to step [latex]2[/latex].

Step [latex]2[/latex] (#[latex]3[/latex]): For each vertex leading to [latex]MR[/latex] (and not leading to a visited vertex) we find the distance to the end. The only vertex to be considered is [latex]A[/latex], since we’ve already visited [latex]Y[/latex] and [latex]P[/latex]. Adding [latex]MR[/latex]’s distance [latex]96[/latex] to the length from [latex]A[/latex] to [latex]MR[/latex] gives the distance [latex]96+79 = 175[/latex] minutes from [latex]A[/latex] to [latex]Y[/latex].

Step [latex]3[/latex] & [latex]4[/latex] (#[latex]3[/latex]): We mark [latex]MR[/latex] as visited, and designate the vertex with smallest recorded distance as current: [latex]NB[/latex]. Back to step [latex]2[/latex].

Step [latex]2[/latex] (#[latex]4[/latex]): For each vertex leading to [latex]NB[/latex], we find the distance to the end. We know the shortest distance from [latex]NB[/latex] to [latex]Y[/latex] is [latex]104[/latex] and the distance from [latex]A[/latex] to [latex]NB[/latex] is [latex]36[/latex], so the distance from [latex]A[/latex] to [latex]Y[/latex] through [latex]NB[/latex] is [latex]104+36 = 140[/latex]. Since this distance is shorter than the previously calculated distance from [latex]Y[/latex] to [latex]A[/latex] through [latex]MR[/latex], we replace it.

Step [latex]3[/latex] & [latex]4[/latex] (#[latex]4[/latex]): We mark [latex]NB[/latex] as visited, and designate [latex]A[/latex] as current, since it now has the shortest distance.

Step [latex]2[/latex] (#[latex]5[/latex]): [latex]T[/latex] is the only non-visited vertex leading to [latex]A[/latex], so we calculate the distance from [latex]T[/latex] to [latex]Y[/latex] through [latex]A[/latex]: [latex]20+140 = 160[/latex] minutes.

Step [latex]3[/latex] & [latex]4[/latex] (#[latex]5[/latex]): We mark [latex]A[/latex] as visited, and designate [latex]E[/latex] as current.

Step [latex]2[/latex] (#[latex]6[/latex]): The only non-visited vertex leading to [latex]E[/latex] is [latex]T[/latex]. Calculating the distance from [latex]T[/latex] to [latex]Y[/latex] through [latex]E[/latex], we compute [latex]172+57 = 229[/latex] minutes. Since this is longer than the existing marked time, we do not replace it.

Step [latex]3[/latex] (#[latex]6[/latex]): We mark [latex]E[/latex] as visited. Since all vertices have been visited, we are done.

From this, we know that the shortest path from Tacoma to Yakima will take [latex]160[/latex] minutes. Tracking which sequence of edges yielded [latex]160[/latex] minutes, we see the shortest path is [latex]T-A-NB-Y[/latex].

Dijkstra’s algorithm is an optimal algorithm, meaning that it always produces the actual shortest path, not just a path that is pretty short, provided one exists. This algorithm is also efficient, meaning that it can be implemented in a reasonable amount of time. Dijkstra’s algorithm takes around [latex]V2[/latex] calculations, where [latex]V[/latex] is the number of vertices in a graph.^[1] A graph with [latex]100[/latex] vertices would take around [latex]10,000[/latex] calculations. While that would be a lot to do by hand, it is not a lot for a computer to handle.

In contrast, an inefficient algorithm might try to list all possible paths and then compute the length of each path. Trying to list all possible paths could easily take [latex]1025[/latex] calculations to compute the shortest path with only [latex]25[/latex] vertices; that’s a [latex]1[/latex] with [latex]25[/latex] zeros after it! To put that in perspective, the fastest computer in the world would still spend over [latex]1000[/latex] years analyzing all those paths.

Efficiency is a hallmark of mathematical practice. When mathematicians seek a proof for something they have conjectured to be true, the most elegant proof is often the most efficient one: an argument that packs the most information in the fewest words, so to speak.

The ideas explored in graph theory are frequently applied to computing algorithms: the language and instructions of software. Since resources are limited (time, computing power), mathematicians and computer scientists seek the most efficient ways to compute. Graph theory helps them find the shortest path from [latex]A[/latex] to [latex]B[/latex].

It can be made to run faster through various optimizations to the implementation. ↵