{"id":1519,"date":"2023-04-10T16:52:27","date_gmt":"2023-04-10T16:52:27","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/?post_type=chapter&p=1519"},"modified":"2024-10-18T20:58:07","modified_gmt":"2024-10-18T20:58:07","slug":"graph-theory-basics-learn-it-2","status":"web-only","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/chapter\/graph-theory-basics-learn-it-2\/","title":{"raw":"Graph Theory Basics: Learn It 2","rendered":"Graph Theory Basics: Learn It 2"},"content":{"raw":"

Shortest Path<\/h2>\r\n

When you use Google Maps to ask for directions from your home to your Aunt\u2019s 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.<\/p>\r\n

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<\/strong> is a step-by-step procedure for solving a problem. Dijkstra\u2019s<\/strong> (pronounced dike-stra) algorithm <\/strong>will find the shortest path between two vertices.<\/p>\r\n

\r\n
\r\n

Dijkstra\u2019s Algorithm<\/h3>\r\n
    \r\n\t
  1. Mark the ending vertex with a distance of zero. Designate this vertex as current.<\/li>\r\n\t
  2. 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\u2019t record this distance if it is longer than a previously recorded distance.<\/li>\r\n\t
  3. Mark the current vertex as visited. We will never look at this vertex again.<\/li>\r\n\t
  4. Mark the vertex with the smallest distance as current, and repeat from step [latex]2[\/latex].<\/li>\r\n<\/ol>\r\n<\/div>\r\n<\/section>\r\n
    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\u2019s 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<\/center>[reveal-answer q=\"703381\"]Show Solution[\/reveal-answer] [hidden-answer a=\"703381\"] Step [latex]1[\/latex]: Mark the ending vertex with a distance of zero. The distances will be recorded in [brackets] after the vertex name.
    \"Graph<\/center>\r\n

     <\/p>\r\n\r\nStep [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<\/center>\r\n

     <\/p>\r\n\r\nStep [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\u2019ve 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].

    \"Graph<\/center>\r\n

     <\/p>\r\n

    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].<\/p>\r\n

    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\u2019ve already visited [latex]Y[\/latex] and [latex]P[\/latex]. Adding [latex]MR[\/latex]\u2019s 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].<\/p>\r\n

    \"Graph<\/center>\r\n

     <\/p>\r\n

    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].<\/p>\r\n

    Step [latex]2[\/latex] (#[latex]4[\/latex]): \u00a0For each vertex leading to [latex]NB[\/latex], we find the distance to the end. \u00a0We 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]. \u00a0Since this distance is shorter than the previously calculated distance from [latex]Y[\/latex] to [latex]A[\/latex] through [latex]MR[\/latex], we replace it.<\/p>\r\n

    \"Graph<\/center>\r\n

     <\/p>\r\n

    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.<\/p>\r\n

    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.<\/p>\r\n

    \"Graph<\/center>\r\n

     <\/p>\r\n

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

     <\/p>\r\n

    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.<\/p>\r\n

     <\/p>\r\n

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

    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].[\/hidden-answer]<\/p>\r\n<\/section>\r\n

    Dijkstra\u2019s algorithm is an optimal algorithm<\/strong>, 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<\/strong>, meaning that it can be implemented in a reasonable amount of time. Dijkstra\u2019s algorithm takes around [latex]V2[\/latex] calculations, where [latex]V[\/latex] is the number of vertices in a graph.[footnote]It can be made to run faster through various optimizations to the implementation.[\/footnote] 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.<\/p>\r\n

    In contrast, an inefficient<\/strong> 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\u2019s 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.<\/p>\r\n

    \r\n

    Efficiency is a hallmark of mathematical practice. When mathematicians seek a proof for something they have conjectured to be true, the most\u00a0elegant<\/em>\u00a0proof is often the most\u00a0efficient<\/em>\u00a0one: an argument that packs the most information in the fewest words, so to speak.<\/p>\r\n

    The ideas explored in graph theory are frequently applied to computing algorithms: the language and instructions of software.\u00a0 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\u00a0[latex]A[\/latex]\u00a0to\u00a0[latex]B[\/latex].<\/p>\r\n<\/section>\r\n

    [ohm2_question hide_question_numbers=1]6904[\/ohm2_question]<\/section>","rendered":"

    Shortest Path<\/h2>\n

    When you use Google Maps to ask for directions from your home to your Aunt\u2019s 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.<\/p>\n

    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<\/strong> is a step-by-step procedure for solving a problem. Dijkstra\u2019s<\/strong> (pronounced dike-stra) algorithm <\/strong>will find the shortest path between two vertices.<\/p>\n

    \n
    \n

    Dijkstra\u2019s Algorithm<\/h3>\n
      \n
    1. Mark the ending vertex with a distance of zero. Designate this vertex as current.<\/li>\n
    2. 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\u2019t record this distance if it is longer than a previously recorded distance.<\/li>\n
    3. Mark the current vertex as visited. We will never look at this vertex again.<\/li>\n
    4. Mark the vertex with the smallest distance as current, and repeat from step [latex]2[\/latex].<\/li>\n<\/ol>\n<\/div>\n<\/section>\n
      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\u2019s 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.<\/p>\n
      \"Graph<\/div>\n