{"id":1505,"date":"2023-04-10T16:28:45","date_gmt":"2023-04-10T16:28:45","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/?post_type=chapter&#038;p=1505"},"modified":"2025-08-29T04:39:57","modified_gmt":"2025-08-29T04:39:57","slug":"graph-theory-basics-fresh-take","status":"web-only","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/chapter\/graph-theory-basics-fresh-take\/","title":{"raw":"Graph Theory Basics: Fresh Take","rendered":"Graph Theory Basics: Fresh Take"},"content":{"raw":"<section class=\"textbox learningGoals\">\r\n<ul>\r\n\t<li>Recognize graph components: vertices, edges, loops, and vertex degrees<\/li>\r\n\t<li>Identify both a path and a circuit through a graph<\/li>\r\n\t<li>Determine whether a graph is connected or disconnected<\/li>\r\n\t<li>Find the shortest path through a graph using Dijkstra's Algorithm<\/li>\r\n<\/ul>\r\n<\/section>\r\n<h2>Drawing Graphs<\/h2>\r\n<div class=\"textbox shaded\">\r\n<p><strong>The Main Idea\u00a0<\/strong><\/p>\r\n\r\nIn the world of Graph Theory, we're not talking about bar graphs or pie charts. Instead, we're diving into a network of dots and lines, known as vertices and edges, that help us solve real-world problems like finding the shortest path in a network. Here, you'll learn about the essential components of a graph, such as vertices, edges, loops, and vertex degrees. You'll also get to know about paths, circuits, and the concept of connected and disconnected graphs. Plus, we'll introduce you to the idea of 'weights' on edges, which can represent various factors like distance or cost.\r\n\r\n<ul>\r\n\t<li><strong>Vertex:<\/strong> Think of it as a meeting point or a junction. In a city map, it could be an intersection.<\/li>\r\n\t<li><strong>Edge:<\/strong> This is the line connecting two vertices. Imagine it as a road linking two intersections.<\/li>\r\n\t<li><strong>Loop:<\/strong> A special edge that starts and ends at the same vertex. Picture a roundabout at an intersection.<\/li>\r\n\t<li><strong>Degree of a Vertex:<\/strong> Count the number of edges meeting at a vertex. It's like counting the number of roads that intersect at a junction.<\/li>\r\n\t<li><strong>Path:<\/strong> A sequence of vertices where you don't repeat any vertex. It's like going from point [latex]A[\/latex] to [latex]B[\/latex] without revisiting any place.<\/li>\r\n\t<li><strong>Circuit:<\/strong> A path that starts and ends at the same vertex. Imagine a circular route that brings you back to where you started.<\/li>\r\n\t<li><strong>Connected Graphs:<\/strong> If you can travel from any vertex to any other vertex, the graph is connected. Think of it as a well-planned city where you can get from any place to another without being stuck.<\/li>\r\n\t<li><strong>Weights:<\/strong> These are special numbers assigned to edges. They can represent distances, costs, or any other metric that matters in your problem.<\/li>\r\n<\/ul>\r\n<\/div>\r\n<section class=\"textbox example\">Back in the 18th century in the Prussian city of K\u00f6nigsberg, a river ran through the city and seven bridges crossed the forks of the river. The river and the bridges are highlighted in the picture below.[footnote]Bogdan Giu\u015fc\u0103. http:\/\/en.wikipedia.org\/wiki\/File:Konigsberg_bridges.png[\/footnote]<center><img class=\"aligncenter wp-image-137\" style=\"font-size: 16px; orphans: 1;\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155115\/Fig2_5_4.png\" alt=\"A map of the city of K\u00f6nigsberg, with the 7 bridges crossing the river highlighted\" width=\"300\" height=\"235\" \/><\/center>\r\n<p>&nbsp;<\/p>\r\n\r\nAs a weekend amusement, the townsfolk would see if they could find a route that would take them across every bridge once and return them to where they started.<\/section>\r\n<p>In the following video we present another view of the K\u00f6nigsberg bridge problem.<\/p>\r\n<section class=\"textbox watchIt\"><iframe title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/yn-OD8OBSDM\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe>\r\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Drawing+a+graph+for+bridges.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cDrawing a graph for bridges\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>\r\n<p>Leonard Euler (pronounced OY-lur), one of the most prolific mathematicians ever, looked at this problem in 1735, laying the foundation for graph theory as a field in mathematics. To analyze this problem, Euler introduced edges representing the bridges:<\/p>\r\n<center>\r\n[caption id=\"attachment_138\" align=\"alignnone\" width=\"500\"]<img class=\"wp-image-138\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155116\/Fig2_5_5.png\" alt=\"A simplified map with four ovals, labeled North Bank, East Bank, South Bank, and Island, respectively. North Bank and South Bank each have two connections to Island and one to East Bank. Island has two connections to North Bank, two connections to South Bank, and one connection to East Bank. East Bank has one connection to North Bank, one to Island, and one to South Bank.\" width=\"500\" height=\"193\" \/> Figure 1. Euler's map of the K\u00f6nigsberg bridge[\/caption]\r\n<\/center>\r\n<p>&nbsp;<\/p>\r\n<p>Since the size of each land mass, it is not relevant to the question of bridge crossings, each can be shrunk down to a vertex representing the location:<\/p>\r\n<center>\r\n[caption id=\"attachment_139\" align=\"alignnone\" width=\"226\"]<img class=\"wp-image-139 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155117\/Fig2_5_6.png\" alt=\"An even further simplified map with four dots, labeled NB, EB, SB, and I, respectively. NB and SB each have two connections to I and one to EB. I has two connections to NB, two connections to SB, and one connection to EB. EB has one connection to NB, one to I, and one to SB.\" width=\"226\" height=\"199\" \/> Figure 2. The shrunken map to a vertex[\/caption]\r\n<\/center>\r\n<p>&nbsp;<\/p>\r\n<p>Notice that in this graph there are <em>two<\/em> edges connecting the north bank and island, corresponding to the two bridges in the original drawing. Depending upon the interpretation of edges and vertices appropriate to a scenario, it is entirely possible and reasonable to have more than one edge connecting two vertices.<\/p>\r\n<p>While we haven\u2019t answered the actual question yet of whether or not there is a route that crosses every bridge once and returns to the starting location, the graph provides the foundation for exploring this question.<\/p>\r\n<p>Watch the following video for more information on graph theory basics. <em>Note: Ignore the assignment at the end of the video<\/em><\/p>\r\n<section class=\"textbox watchIt\"><iframe src=\"\/\/plugin.3playmedia.com\/show?mf=11328614&amp;p3sdk_version=1.10.1&amp;p=20361&amp;pt=375&amp;video_id=ZHqQDA3be-k&amp;video_target=tpm-plugin-bgbkwcvo-ZHqQDA3be-k\" width=\"800px\" height=\"450px\" frameborder=\"0\" marginwidth=\"0px\" marginheight=\"0px\"><\/iframe>\r\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Basic+Concepts+in+Graph+Theory.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cBasic Concepts in Graph Theory\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>\r\n<h2>Shortest Path<\/h2>\r\n<div class=\"textbox shaded\">\r\n<p><strong>The Main Idea\u00a0<\/strong><\/p>\r\n\r\nEver wondered how Google Maps finds the quickest route for you? It's not magic; it's Graph Theory in action! This section dives deeper into the concept of finding the shortest path in a graph using algorithms, specifically Dijkstra's Algorithm. Algorithms are your step-by-step guides to solving complex problems. Dijkstra's Algorithm not only finds the shortest path but does so efficiently, saving both time and computational resources.\r\n\r\n<ul>\r\n\t<li><strong>Shortest Path:<\/strong> It's not always about the distance; sometimes it's about time or even cost. Always consider the 'weights' on the edges.<\/li>\r\n\t<li><strong>Dijkstra's Algorithm:<\/strong> This is your go-to for finding the shortest path. It starts with marking the end vertex and works its way back, calculating distances.<\/li>\r\n\t<li>Steps to find the shortest path between two vertices using the Dijkstra\u2019s Algorithm:\r\n\r\n<ol style=\"list-style-type: decimal;\">\r\n\t<li>Mark the ending vertex with a distance of zero. Designate this vertex as current.<\/li>\r\n\t<li>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<li>Mark the current vertex as visited. We will never look at this vertex again.<\/li>\r\n\t<li>Mark the vertex with the smallest distance as current, and repeat from step [latex]2[\/latex].<\/li>\r\n<\/ol>\r\n<\/li>\r\n\t<li><strong>Efficiency:<\/strong> In the world of algorithms, efficiency is key. Dijkstra's Algorithm is both optimal and efficient, making it a popular choice for many applications.<\/li>\r\n\t<li><strong>Calculations:<\/strong> The number of calculations needed for Dijkstra's Algorithm is around [latex]V^2[\/latex], where [latex]V[\/latex] is the number of vertices. Efficient, isn't it?<\/li>\r\n<\/ul>\r\n<\/div>\r\n<section class=\"textbox example\">A shipping company needs to route a package from Washington, D.C. to San Diego, CA. To minimize costs, the package will first be sent to their processing center in Baltimore, MD then sent as part of mass shipments between their various processing centers, ending up in their processing center in Bakersfield, CA. From there it will be delivered in a small truck to San Diego.The travel times, in hours, between their processing centers are shown in the table below. Three hours has been added to each travel time for processing. Find the shortest path from Baltimore to Bakersfield.\r\n\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td>&nbsp;<\/td>\r\n<td>Baltimore<\/td>\r\n<td>Denver<\/td>\r\n<td>Dallas<\/td>\r\n<td>Chicago<\/td>\r\n<td>Atlanta<\/td>\r\n<td>Bakersfield<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Baltimore<\/td>\r\n<td>*<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>&nbsp;<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Denver<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>*<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>[latex]24[\/latex]<\/td>\r\n<td>[latex]19[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Dallas<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>*<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]25[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Chicago<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>*<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>&nbsp;<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Atlanta<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>[latex]24[\/latex]<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>*<\/td>\r\n<td>&nbsp;<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Bakersfield<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>[latex]19[\/latex]<\/td>\r\n<td>[latex]25[\/latex]<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>*<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<div>[reveal-answer q=\"703381\"]Show Solution[\/reveal-answer]<br \/>\r\n[hidden-answer a=\"703381\"]<br \/>\r\nWhile we could draw a graph, we can also work directly from the table.\r\n\r\n<ol>\r\n\t<li>Step [latex]1[\/latex]: The ending vertex, Bakersfield, is marked as current.<\/li>\r\n\t<li>Step [latex]2[\/latex]: All cities connected to Bakersfield, in this case Denver and Dallas, have their distances calculated; we\u2019ll mark those distances in the column headers.<\/li>\r\n\t<li>Step [latex]3[\/latex] &amp; [latex]4[\/latex]: Mark Bakersfield as visited.<\/li>\r\n<\/ol>\r\n\r\nHere, we are doing it by shading the corresponding row and column of the table. We mark Denver as current, shown in bold, since it is the vertex with the shortest distance.\r\n\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td>&nbsp;<\/td>\r\n<td>Baltimore<\/td>\r\n<td><strong>Denver<\/strong> [latex][19][\/latex]<\/td>\r\n<td>Dallas [latex][25][\/latex]<\/td>\r\n<td>Chicago<\/td>\r\n<td>Atlanta<\/td>\r\n<td>Bakersfield [latex][0][\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Baltimore<\/td>\r\n<td>*<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>&nbsp;<\/td>\r\n<\/tr>\r\n<tr>\r\n<td><strong>Denver<\/strong><\/td>\r\n<td>&nbsp;<\/td>\r\n<td>*<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>[latex]24[\/latex]<\/td>\r\n<td>[latex]19[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Dallas<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>*<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]25[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Chicago<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>*<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>&nbsp;<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Atlanta<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>[latex]24[\/latex]<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>*<\/td>\r\n<td>&nbsp;<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Bakersfield<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>[latex]19[\/latex]<\/td>\r\n<td>[latex]25[\/latex]<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>*<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<div>\r\n<p>&nbsp;<\/p>\r\n<p>Step [latex]2[\/latex] (#[latex]2[\/latex]): For cities connected to Denver, calculate distance to the end. For example, Chicago is [latex]18[\/latex] hours from Denver, and Denver is [latex]19[\/latex] hours from the end, the distance for Chicago to the end is [latex]18+19 = 37[\/latex] (Chicago to Denver to Bakersfield). Atlanta is [latex]24[\/latex] hours from Denver, so the distance to the end is [latex]24+19 = 43[\/latex] (Atlanta to Denver to Bakersfield).<\/p>\r\n<p>Step [latex]3[\/latex] &amp; [latex]4[\/latex] (#[latex]2[\/latex]): We mark Denver as visited and mark Dallas as current.<\/p>\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td>&nbsp;<\/td>\r\n<td>Baltimore<\/td>\r\n<td>Denver [latex][19][\/latex]<\/td>\r\n<td><strong>Dallas<\/strong> [latex][25][\/latex]<\/td>\r\n<td>Chicago [latex][37][\/latex]<\/td>\r\n<td>Atlanta [latex][43][\/latex]<\/td>\r\n<td>Bakersfield [latex][0][\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Baltimore<\/td>\r\n<td>*<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>&nbsp;<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Denver<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>*<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>[latex]24[\/latex]<\/td>\r\n<td>[latex]19[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td><strong>Dallas<\/strong><\/td>\r\n<td>&nbsp;<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>*<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]25[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Chicago<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>*<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>&nbsp;<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Atlanta<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>[latex]24[\/latex]<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>*<\/td>\r\n<td>&nbsp;<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Bakersfield<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>[latex]19[\/latex]<\/td>\r\n<td>[latex]25[\/latex]<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>*<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<div>\r\n<p>&nbsp;<\/p>\r\n<p>Step [latex]2[\/latex] (#[latex]3[\/latex]): For cities connected to Dallas, calculate the distance to the end. For Chicago, the distance from Chicago to Dallas is [latex]18[\/latex] and from Dallas to the end is [latex]25[\/latex], so the distance from Chicago to the end through Dallas would be [latex]18+25 = 43[\/latex]. Since this is longer than the currently marked distance for Chicago, we do not replace it. For Atlanta, we calculate [latex]15+25 = 40[\/latex]. Since this is shorter than the currently marked distance for Atlanta, we replace the existing distance.<\/p>\r\n<p>Step [latex]3[\/latex] &amp; [latex]4[\/latex] (#[latex]3[\/latex]): We mark Dallas as visited, and mark Chicago as current.<\/p>\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td>&nbsp;<\/td>\r\n<td>Baltimore<\/td>\r\n<td>Denver [latex][19][\/latex]<\/td>\r\n<td>Dallas [latex][25][\/latex]<\/td>\r\n<td><strong>Chicago<\/strong> [latex][37][\/latex]<\/td>\r\n<td>Atlanta [latex][40][\/latex]<\/td>\r\n<td>Bakersfield [latex][0][\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Baltimore<\/td>\r\n<td>*<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>&nbsp;<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Denver<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>*<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>[latex]24[\/latex]<\/td>\r\n<td>[latex]19[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Dallas<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>*<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]25[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td><strong>Chicago<\/strong><\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>*<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>&nbsp;<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Atlanta<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>[latex]24[\/latex]<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>*<\/td>\r\n<td>&nbsp;<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Bakersfield<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>[latex]19[\/latex]<\/td>\r\n<td>[latex]25[\/latex]<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>*<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<div>\r\n<p>&nbsp;<\/p>\r\n<p>Step [latex]2[\/latex] (#[latex]4[\/latex]): Baltimore and Atlanta are the only non-visited cities connected to Chicago. For Baltimore, we calculate [latex]15+37 = 52[\/latex] and mark that distance. For Atlanta, we calculate [latex]14+37 = 51[\/latex]. Since this is longer than the existing distance of [latex]40[\/latex] for Atlanta, we do not replace that distance.<\/p>\r\n<p>Step [latex]3[\/latex] &amp; [latex]4[\/latex] (#[latex]4)[\/latex]): Mark Chicago as visited and Atlanta as current.<\/p>\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td>&nbsp;<\/td>\r\n<td>Baltimore [latex][52][\/latex]<\/td>\r\n<td>Denver [latex][19][\/latex]<\/td>\r\n<td>Dallas [latex][25][\/latex]<\/td>\r\n<td>Chicago [latex][37][\/latex]<\/td>\r\n<td><strong>Atlanta<\/strong> [latex][40][\/latex]<\/td>\r\n<td>Bakersfield [latex][0][\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Baltimore<\/td>\r\n<td>*<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>&nbsp;<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Denver<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>*<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>[latex]24[\/latex]<\/td>\r\n<td>[latex]19[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Dallas<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>*<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]25[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Chicago<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>[latex]18[\/latex]<\/td>\r\n<td>*<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>&nbsp;<\/td>\r\n<\/tr>\r\n<tr>\r\n<td><strong>Atlanta<\/strong><\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>[latex]24[\/latex]<\/td>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]14[\/latex]<\/td>\r\n<td>*<\/td>\r\n<td>&nbsp;<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Bakersfield<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>[latex]19[\/latex]<\/td>\r\n<td>[latex]25[\/latex]<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>&nbsp;<\/td>\r\n<td>*<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<div>\r\n<p>&nbsp;<\/p>\r\n<p>Step [latex]2[\/latex] (#[latex]5[\/latex]): The distance from Atlanta to Baltimore is [latex]14[\/latex]. Adding that to the distance already calculated for Atlanta gives a total distance of [latex]14+40 = 54[\/latex] hours from Baltimore to Bakersfield through Atlanta. Since this is larger than the currently calculated distance, we do not replace the distance for Baltimore.<\/p>\r\n<p>Step [latex]3[\/latex] &amp; [latex]4[\/latex] (#[latex]5[\/latex]): We mark Atlanta as visited. All cities have been visited and we are done.<\/p>\r\n<p>The shortest route from Baltimore to Bakersfield will take [latex]52[\/latex] hours, and will route through Chicago and Denver.<\/p>\r\n<p>[\/hidden-answer]<\/p>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/section>\r\n<section class=\"textbox watchIt\"><iframe title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/KvRwplnIoEM\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe>\r\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory_+Dijkstra's+Algorithm.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: Dijkstra's Algorithm\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>\r\n<p>For more information on Dijkstra's Algorithm, watch the following video.<\/p>\r\n<section class=\"textbox watchIt\"><iframe title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/GazC3A4OQTE?si=O7X6SG1lwYwfgcln\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe>\r\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Dijkstra's+Algorithm+-+Computerphile.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cDijkstra's Algorithm - Computerphile\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>\r\n<p>If you are curious what an algorithm is, the following video goes into algorithms in more detail.<\/p>\r\n<section class=\"textbox watchIt\"><iframe title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/6hfOvs8pY1k?si=3GWKjJ2WsYiuB_Jt\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe>\r\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/What's+an+algorithm_+-+David+J.+Malan.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cWhat's an algorithm? - David J. Malan\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>","rendered":"<section class=\"textbox learningGoals\">\n<ul>\n<li>Recognize graph components: vertices, edges, loops, and vertex degrees<\/li>\n<li>Identify both a path and a circuit through a graph<\/li>\n<li>Determine whether a graph is connected or disconnected<\/li>\n<li>Find the shortest path through a graph using Dijkstra&#8217;s Algorithm<\/li>\n<\/ul>\n<\/section>\n<h2>Drawing Graphs<\/h2>\n<div class=\"textbox shaded\">\n<p><strong>The Main Idea\u00a0<\/strong><\/p>\n<p>In the world of Graph Theory, we&#8217;re not talking about bar graphs or pie charts. Instead, we&#8217;re diving into a network of dots and lines, known as vertices and edges, that help us solve real-world problems like finding the shortest path in a network. Here, you&#8217;ll learn about the essential components of a graph, such as vertices, edges, loops, and vertex degrees. You&#8217;ll also get to know about paths, circuits, and the concept of connected and disconnected graphs. Plus, we&#8217;ll introduce you to the idea of &#8216;weights&#8217; on edges, which can represent various factors like distance or cost.<\/p>\n<ul>\n<li><strong>Vertex:<\/strong> Think of it as a meeting point or a junction. In a city map, it could be an intersection.<\/li>\n<li><strong>Edge:<\/strong> This is the line connecting two vertices. Imagine it as a road linking two intersections.<\/li>\n<li><strong>Loop:<\/strong> A special edge that starts and ends at the same vertex. Picture a roundabout at an intersection.<\/li>\n<li><strong>Degree of a Vertex:<\/strong> Count the number of edges meeting at a vertex. It&#8217;s like counting the number of roads that intersect at a junction.<\/li>\n<li><strong>Path:<\/strong> A sequence of vertices where you don&#8217;t repeat any vertex. It&#8217;s like going from point [latex]A[\/latex] to [latex]B[\/latex] without revisiting any place.<\/li>\n<li><strong>Circuit:<\/strong> A path that starts and ends at the same vertex. Imagine a circular route that brings you back to where you started.<\/li>\n<li><strong>Connected Graphs:<\/strong> If you can travel from any vertex to any other vertex, the graph is connected. Think of it as a well-planned city where you can get from any place to another without being stuck.<\/li>\n<li><strong>Weights:<\/strong> These are special numbers assigned to edges. They can represent distances, costs, or any other metric that matters in your problem.<\/li>\n<\/ul>\n<\/div>\n<section class=\"textbox example\">Back in the 18th century in the Prussian city of K\u00f6nigsberg, a river ran through the city and seven bridges crossed the forks of the river. The river and the bridges are highlighted in the picture below.<a class=\"footnote\" title=\"Bogdan Giu\u015fc\u0103. http:\/\/en.wikipedia.org\/wiki\/File:Konigsberg_bridges.png\" id=\"return-footnote-1505-1\" href=\"#footnote-1505-1\" aria-label=\"Footnote 1\"><sup class=\"footnote\">[1]<\/sup><\/a><\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-137\" style=\"font-size: 16px; orphans: 1;\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155115\/Fig2_5_4.png\" alt=\"A map of the city of K\u00f6nigsberg, with the 7 bridges crossing the river highlighted\" width=\"300\" height=\"235\" \/><\/div>\n<p>&nbsp;<\/p>\n<p>As a weekend amusement, the townsfolk would see if they could find a route that would take them across every bridge once and return them to where they started.<\/section>\n<p>In the following video we present another view of the K\u00f6nigsberg bridge problem.<\/p>\n<section class=\"textbox watchIt\"><iframe loading=\"lazy\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/yn-OD8OBSDM\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Drawing+a+graph+for+bridges.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cDrawing a graph for bridges\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<p>Leonard Euler (pronounced OY-lur), one of the most prolific mathematicians ever, looked at this problem in 1735, laying the foundation for graph theory as a field in mathematics. To analyze this problem, Euler introduced edges representing the bridges:<\/p>\n<div style=\"text-align: center;\">\n<figure id=\"attachment_138\" aria-describedby=\"caption-attachment-138\" style=\"width: 500px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-138\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155116\/Fig2_5_5.png\" alt=\"A simplified map with four ovals, labeled North Bank, East Bank, South Bank, and Island, respectively. North Bank and South Bank each have two connections to Island and one to East Bank. Island has two connections to North Bank, two connections to South Bank, and one connection to East Bank. East Bank has one connection to North Bank, one to Island, and one to South Bank.\" width=\"500\" height=\"193\" \/><figcaption id=\"caption-attachment-138\" class=\"wp-caption-text\">Figure 1. Euler&#8217;s map of the K\u00f6nigsberg bridge<\/figcaption><\/figure>\n<\/div>\n<p>&nbsp;<\/p>\n<p>Since the size of each land mass, it is not relevant to the question of bridge crossings, each can be shrunk down to a vertex representing the location:<\/p>\n<div style=\"text-align: center;\">\n<figure id=\"attachment_139\" aria-describedby=\"caption-attachment-139\" style=\"width: 226px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-139 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155117\/Fig2_5_6.png\" alt=\"An even further simplified map with four dots, labeled NB, EB, SB, and I, respectively. NB and SB each have two connections to I and one to EB. I has two connections to NB, two connections to SB, and one connection to EB. EB has one connection to NB, one to I, and one to SB.\" width=\"226\" height=\"199\" \/><figcaption id=\"caption-attachment-139\" class=\"wp-caption-text\">Figure 2. The shrunken map to a vertex<\/figcaption><\/figure>\n<\/div>\n<p>&nbsp;<\/p>\n<p>Notice that in this graph there are <em>two<\/em> edges connecting the north bank and island, corresponding to the two bridges in the original drawing. Depending upon the interpretation of edges and vertices appropriate to a scenario, it is entirely possible and reasonable to have more than one edge connecting two vertices.<\/p>\n<p>While we haven\u2019t answered the actual question yet of whether or not there is a route that crosses every bridge once and returns to the starting location, the graph provides the foundation for exploring this question.<\/p>\n<p>Watch the following video for more information on graph theory basics. <em>Note: Ignore the assignment at the end of the video<\/em><\/p>\n<section class=\"textbox watchIt\"><iframe loading=\"lazy\" src=\"\/\/plugin.3playmedia.com\/show?mf=11328614&amp;p3sdk_version=1.10.1&amp;p=20361&amp;pt=375&amp;video_id=ZHqQDA3be-k&amp;video_target=tpm-plugin-bgbkwcvo-ZHqQDA3be-k\" width=\"800px\" height=\"450px\" frameborder=\"0\" marginwidth=\"0px\" marginheight=\"0px\"><\/iframe><\/p>\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Basic+Concepts+in+Graph+Theory.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cBasic Concepts in Graph Theory\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<h2>Shortest Path<\/h2>\n<div class=\"textbox shaded\">\n<p><strong>The Main Idea\u00a0<\/strong><\/p>\n<p>Ever wondered how Google Maps finds the quickest route for you? It&#8217;s not magic; it&#8217;s Graph Theory in action! This section dives deeper into the concept of finding the shortest path in a graph using algorithms, specifically Dijkstra&#8217;s Algorithm. Algorithms are your step-by-step guides to solving complex problems. Dijkstra&#8217;s Algorithm not only finds the shortest path but does so efficiently, saving both time and computational resources.<\/p>\n<ul>\n<li><strong>Shortest Path:<\/strong> It&#8217;s not always about the distance; sometimes it&#8217;s about time or even cost. Always consider the &#8216;weights&#8217; on the edges.<\/li>\n<li><strong>Dijkstra&#8217;s Algorithm:<\/strong> This is your go-to for finding the shortest path. It starts with marking the end vertex and works its way back, calculating distances.<\/li>\n<li>Steps to find the shortest path between two vertices using the Dijkstra\u2019s Algorithm:\n<ol style=\"list-style-type: decimal;\">\n<li>Mark the ending vertex with a distance of zero. Designate this vertex as current.<\/li>\n<li>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<li>Mark the current vertex as visited. We will never look at this vertex again.<\/li>\n<li>Mark the vertex with the smallest distance as current, and repeat from step [latex]2[\/latex].<\/li>\n<\/ol>\n<\/li>\n<li><strong>Efficiency:<\/strong> In the world of algorithms, efficiency is key. Dijkstra&#8217;s Algorithm is both optimal and efficient, making it a popular choice for many applications.<\/li>\n<li><strong>Calculations:<\/strong> The number of calculations needed for Dijkstra&#8217;s Algorithm is around [latex]V^2[\/latex], where [latex]V[\/latex] is the number of vertices. Efficient, isn&#8217;t it?<\/li>\n<\/ul>\n<\/div>\n<section class=\"textbox example\">A shipping company needs to route a package from Washington, D.C. to San Diego, CA. To minimize costs, the package will first be sent to their processing center in Baltimore, MD then sent as part of mass shipments between their various processing centers, ending up in their processing center in Bakersfield, CA. From there it will be delivered in a small truck to San Diego.The travel times, in hours, between their processing centers are shown in the table below. Three hours has been added to each travel time for processing. Find the shortest path from Baltimore to Bakersfield.<\/p>\n<table>\n<tbody>\n<tr>\n<td>&nbsp;<\/td>\n<td>Baltimore<\/td>\n<td>Denver<\/td>\n<td>Dallas<\/td>\n<td>Chicago<\/td>\n<td>Atlanta<\/td>\n<td>Bakersfield<\/td>\n<\/tr>\n<tr>\n<td>Baltimore<\/td>\n<td>*<\/td>\n<td>&nbsp;<\/td>\n<td>&nbsp;<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td>Denver<\/td>\n<td>&nbsp;<\/td>\n<td>*<\/td>\n<td>&nbsp;<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>[latex]24[\/latex]<\/td>\n<td>[latex]19[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Dallas<\/td>\n<td>&nbsp;<\/td>\n<td>&nbsp;<\/td>\n<td>*<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]25[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Chicago<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>*<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td>Atlanta<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>[latex]24[\/latex]<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>*<\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td>Bakersfield<\/td>\n<td>&nbsp;<\/td>\n<td>[latex]19[\/latex]<\/td>\n<td>[latex]25[\/latex]<\/td>\n<td>&nbsp;<\/td>\n<td>&nbsp;<\/td>\n<td>*<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div>\n<div class=\"qa-wrapper\" style=\"display: block\"><button class=\"show-answer show-answer-button collapsed\" data-target=\"q703381\">Show Solution<\/button><\/p>\n<div id=\"q703381\" class=\"hidden-answer\" style=\"display: none\">\nWhile we could draw a graph, we can also work directly from the table.<\/p>\n<ol>\n<li>Step [latex]1[\/latex]: The ending vertex, Bakersfield, is marked as current.<\/li>\n<li>Step [latex]2[\/latex]: All cities connected to Bakersfield, in this case Denver and Dallas, have their distances calculated; we\u2019ll mark those distances in the column headers.<\/li>\n<li>Step [latex]3[\/latex] &amp; [latex]4[\/latex]: Mark Bakersfield as visited.<\/li>\n<\/ol>\n<p>Here, we are doing it by shading the corresponding row and column of the table. We mark Denver as current, shown in bold, since it is the vertex with the shortest distance.<\/p>\n<table>\n<tbody>\n<tr>\n<td>&nbsp;<\/td>\n<td>Baltimore<\/td>\n<td><strong>Denver<\/strong> [latex][19][\/latex]<\/td>\n<td>Dallas [latex][25][\/latex]<\/td>\n<td>Chicago<\/td>\n<td>Atlanta<\/td>\n<td>Bakersfield [latex][0][\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Baltimore<\/td>\n<td>*<\/td>\n<td>&nbsp;<\/td>\n<td>&nbsp;<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td><strong>Denver<\/strong><\/td>\n<td>&nbsp;<\/td>\n<td>*<\/td>\n<td>&nbsp;<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>[latex]24[\/latex]<\/td>\n<td>[latex]19[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Dallas<\/td>\n<td>&nbsp;<\/td>\n<td>&nbsp;<\/td>\n<td>*<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]25[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Chicago<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>*<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td>Atlanta<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>[latex]24[\/latex]<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>*<\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td>Bakersfield<\/td>\n<td>&nbsp;<\/td>\n<td>[latex]19[\/latex]<\/td>\n<td>[latex]25[\/latex]<\/td>\n<td>&nbsp;<\/td>\n<td>&nbsp;<\/td>\n<td>*<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div>\n<p>&nbsp;<\/p>\n<p>Step [latex]2[\/latex] (#[latex]2[\/latex]): For cities connected to Denver, calculate distance to the end. For example, Chicago is [latex]18[\/latex] hours from Denver, and Denver is [latex]19[\/latex] hours from the end, the distance for Chicago to the end is [latex]18+19 = 37[\/latex] (Chicago to Denver to Bakersfield). Atlanta is [latex]24[\/latex] hours from Denver, so the distance to the end is [latex]24+19 = 43[\/latex] (Atlanta to Denver to Bakersfield).<\/p>\n<p>Step [latex]3[\/latex] &amp; [latex]4[\/latex] (#[latex]2[\/latex]): We mark Denver as visited and mark Dallas as current.<\/p>\n<table>\n<tbody>\n<tr>\n<td>&nbsp;<\/td>\n<td>Baltimore<\/td>\n<td>Denver [latex][19][\/latex]<\/td>\n<td><strong>Dallas<\/strong> [latex][25][\/latex]<\/td>\n<td>Chicago [latex][37][\/latex]<\/td>\n<td>Atlanta [latex][43][\/latex]<\/td>\n<td>Bakersfield [latex][0][\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Baltimore<\/td>\n<td>*<\/td>\n<td>&nbsp;<\/td>\n<td>&nbsp;<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td>Denver<\/td>\n<td>&nbsp;<\/td>\n<td>*<\/td>\n<td>&nbsp;<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>[latex]24[\/latex]<\/td>\n<td>[latex]19[\/latex]<\/td>\n<\/tr>\n<tr>\n<td><strong>Dallas<\/strong><\/td>\n<td>&nbsp;<\/td>\n<td>&nbsp;<\/td>\n<td>*<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]25[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Chicago<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>*<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td>Atlanta<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>[latex]24[\/latex]<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>*<\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td>Bakersfield<\/td>\n<td>&nbsp;<\/td>\n<td>[latex]19[\/latex]<\/td>\n<td>[latex]25[\/latex]<\/td>\n<td>&nbsp;<\/td>\n<td>&nbsp;<\/td>\n<td>*<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div>\n<p>&nbsp;<\/p>\n<p>Step [latex]2[\/latex] (#[latex]3[\/latex]): For cities connected to Dallas, calculate the distance to the end. For Chicago, the distance from Chicago to Dallas is [latex]18[\/latex] and from Dallas to the end is [latex]25[\/latex], so the distance from Chicago to the end through Dallas would be [latex]18+25 = 43[\/latex]. Since this is longer than the currently marked distance for Chicago, we do not replace it. For Atlanta, we calculate [latex]15+25 = 40[\/latex]. Since this is shorter than the currently marked distance for Atlanta, we replace the existing distance.<\/p>\n<p>Step [latex]3[\/latex] &amp; [latex]4[\/latex] (#[latex]3[\/latex]): We mark Dallas as visited, and mark Chicago as current.<\/p>\n<table>\n<tbody>\n<tr>\n<td>&nbsp;<\/td>\n<td>Baltimore<\/td>\n<td>Denver [latex][19][\/latex]<\/td>\n<td>Dallas [latex][25][\/latex]<\/td>\n<td><strong>Chicago<\/strong> [latex][37][\/latex]<\/td>\n<td>Atlanta [latex][40][\/latex]<\/td>\n<td>Bakersfield [latex][0][\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Baltimore<\/td>\n<td>*<\/td>\n<td>&nbsp;<\/td>\n<td>&nbsp;<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td>Denver<\/td>\n<td>&nbsp;<\/td>\n<td>*<\/td>\n<td>&nbsp;<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>[latex]24[\/latex]<\/td>\n<td>[latex]19[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Dallas<\/td>\n<td>&nbsp;<\/td>\n<td>&nbsp;<\/td>\n<td>*<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]25[\/latex]<\/td>\n<\/tr>\n<tr>\n<td><strong>Chicago<\/strong><\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>*<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td>Atlanta<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>[latex]24[\/latex]<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>*<\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td>Bakersfield<\/td>\n<td>&nbsp;<\/td>\n<td>[latex]19[\/latex]<\/td>\n<td>[latex]25[\/latex]<\/td>\n<td>&nbsp;<\/td>\n<td>&nbsp;<\/td>\n<td>*<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div>\n<p>&nbsp;<\/p>\n<p>Step [latex]2[\/latex] (#[latex]4[\/latex]): Baltimore and Atlanta are the only non-visited cities connected to Chicago. For Baltimore, we calculate [latex]15+37 = 52[\/latex] and mark that distance. For Atlanta, we calculate [latex]14+37 = 51[\/latex]. Since this is longer than the existing distance of [latex]40[\/latex] for Atlanta, we do not replace that distance.<\/p>\n<p>Step [latex]3[\/latex] &amp; [latex]4[\/latex] (#[latex]4)[\/latex]): Mark Chicago as visited and Atlanta as current.<\/p>\n<table>\n<tbody>\n<tr>\n<td>&nbsp;<\/td>\n<td>Baltimore [latex][52][\/latex]<\/td>\n<td>Denver [latex][19][\/latex]<\/td>\n<td>Dallas [latex][25][\/latex]<\/td>\n<td>Chicago [latex][37][\/latex]<\/td>\n<td><strong>Atlanta<\/strong> [latex][40][\/latex]<\/td>\n<td>Bakersfield [latex][0][\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Baltimore<\/td>\n<td>*<\/td>\n<td>&nbsp;<\/td>\n<td>&nbsp;<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td>Denver<\/td>\n<td>&nbsp;<\/td>\n<td>*<\/td>\n<td>&nbsp;<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>[latex]24[\/latex]<\/td>\n<td>[latex]19[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Dallas<\/td>\n<td>&nbsp;<\/td>\n<td>&nbsp;<\/td>\n<td>*<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]25[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Chicago<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>[latex]18[\/latex]<\/td>\n<td>*<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td><strong>Atlanta<\/strong><\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>[latex]24[\/latex]<\/td>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]14[\/latex]<\/td>\n<td>*<\/td>\n<td>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td>Bakersfield<\/td>\n<td>&nbsp;<\/td>\n<td>[latex]19[\/latex]<\/td>\n<td>[latex]25[\/latex]<\/td>\n<td>&nbsp;<\/td>\n<td>&nbsp;<\/td>\n<td>*<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div>\n<p>&nbsp;<\/p>\n<p>Step [latex]2[\/latex] (#[latex]5[\/latex]): The distance from Atlanta to Baltimore is [latex]14[\/latex]. Adding that to the distance already calculated for Atlanta gives a total distance of [latex]14+40 = 54[\/latex] hours from Baltimore to Bakersfield through Atlanta. Since this is larger than the currently calculated distance, we do not replace the distance for Baltimore.<\/p>\n<p>Step [latex]3[\/latex] &amp; [latex]4[\/latex] (#[latex]5[\/latex]): We mark Atlanta as visited. All cities have been visited and we are done.<\/p>\n<p>The shortest route from Baltimore to Bakersfield will take [latex]52[\/latex] hours, and will route through Chicago and Denver.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/section>\n<section class=\"textbox watchIt\"><iframe loading=\"lazy\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/KvRwplnIoEM\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory_+Dijkstra's+Algorithm.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: Dijkstra&#8217;s Algorithm\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<p>For more information on Dijkstra&#8217;s Algorithm, watch the following video.<\/p>\n<section class=\"textbox watchIt\"><iframe loading=\"lazy\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/GazC3A4OQTE?si=O7X6SG1lwYwfgcln\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Dijkstra's+Algorithm+-+Computerphile.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cDijkstra&#8217;s Algorithm &#8211; Computerphile\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<p>If you are curious what an algorithm is, the following video goes into algorithms in more detail.<\/p>\n<section class=\"textbox watchIt\"><iframe loading=\"lazy\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/6hfOvs8pY1k?si=3GWKjJ2WsYiuB_Jt\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/What's+an+algorithm_+-+David+J.+Malan.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cWhat&#8217;s an algorithm? &#8211; David J. Malan\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<hr class=\"before-footnotes clear\" \/><div class=\"footnotes\"><ol><li id=\"footnote-1505-1\">Bogdan Giu\u015fc\u0103. http:\/\/en.wikipedia.org\/wiki\/File:Konigsberg_bridges.png <a href=\"#return-footnote-1505-1\" class=\"return-footnote\" aria-label=\"Return to footnote 1\">&crarr;<\/a><\/li><\/ol><\/div>","protected":false},"author":15,"menu_order":8,"template":"","meta":{"_candela_citation":"[{\"type\":\"original\",\"description\":\"Revision and Adaptation\",\"author\":\"\",\"organization\":\"Lumen Learning\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Math in Society\",\"author\":\"David Lippman\",\"organization\":\"\",\"url\":\"http:\/\/www.opentextbookstore.com\/mathinsociety\/\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"copyrighted_video\",\"description\":\"Drawing a graph for bridges\",\"author\":\" OCLPhase2\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/yn-OD8OBSDM\",\"project\":\"\",\"license\":\"arr\",\"license_terms\":\"\"},{\"type\":\"copyrighted_video\",\"description\":\"Basic Concepts in Graph Theory\",\"author\":\"Ohio State MSLC\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/ZHqQDA3be-k\",\"project\":\"\",\"license\":\"arr\",\"license_terms\":\"\"},{\"type\":\"copyrighted_video\",\"description\":\"Graph Theory: Dijkstra\\'s Algorithm\",\"author\":\"James Sousa (Mathispower4u.com)\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/KvRwplnIoEM\",\"project\":\"\",\"license\":\"arr\",\"license_terms\":\"\"},{\"type\":\"copyrighted_video\",\"description\":\"Dijkstra\\'s Algorithm - Computerphile\",\"author\":\"Computerphile\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/GazC3A4OQTE\",\"project\":\"\",\"license\":\"arr\",\"license_terms\":\"\"},{\"type\":\"copyrighted_video\",\"description\":\"What\\'s an algorithm? - David J. Malan\",\"author\":\"TED-Ed\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/6hfOvs8pY1k\",\"project\":\"\",\"license\":\"arr\",\"license_terms\":\"\"}]","pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"part":75,"module-header":"fresh_take","content_attributions":null,"internal_book_links":[],"video_content":null,"cc_video_embed_content":{"cc_scripts":"","media_targets":[]},"try_it_collection":null,"_links":{"self":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/1505"}],"collection":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/users\/15"}],"version-history":[{"count":36,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/1505\/revisions"}],"predecessor-version":[{"id":15923,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/1505\/revisions\/15923"}],"part":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/parts\/75"}],"metadata":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/1505\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/media?parent=1505"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapter-type?post=1505"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/contributor?post=1505"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/license?post=1505"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}