{"id":206,"date":"2017-06-13T23:22:19","date_gmt":"2017-06-13T23:22:19","guid":{"rendered":"https:\/\/courses.lumenlearning.com\/suny-hccc-ma-124-1\/?post_type=chapter&#038;p=206"},"modified":"2018-08-14T20:28:14","modified_gmt":"2018-08-14T20:28:14","slug":"graph-theory-basics","status":"publish","type":"chapter","link":"https:\/\/courses.lumenlearning.com\/suny-hccc-ma-124-1\/chapter\/graph-theory-basics\/","title":{"raw":"Graph Theory Basics","rendered":"Graph Theory Basics"},"content":{"raw":"In this lesson, we will introduce Graph Theory, a field of mathematics that started approximately 300 years ago to help solve problems such as finding the shortest path between two locations.\r\n\r\nNow, elements of graph theory are used to optimize a wide range of\u00a0systems, generate friend suggestions on social media, and plan complex shipping and air traffic routes.\r\n<div class=\"textbox learning-objectives\">\r\n<h3>Learning Objectives<\/h3>\r\nIn this lesson you will learn how to:\r\n<ul>\r\n \t<li>Identify the vertices, edges, and loops of a graph<\/li>\r\n \t<li>Identify the degree of a vertex<\/li>\r\n \t<li>Identify and draw 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<\/div>\r\n<h2>Elements of Graph Theory<\/h2>\r\nIn the modern world, planning efficient routes is essential for business and industry, with applications as varied as product distribution, laying new fiber optic lines for broadband internet, and suggesting new friends within social network websites like Facebook.\r\n\r\nThis field of mathematics started nearly 300 years ago as a look into a mathematical puzzle (we\u2019ll look at it in a bit). The field has exploded in importance in the last century, both because of the growing complexity of business in a global economy and because of the computational power that computers have provided us.\r\n<h3>Drawing Graphs<\/h3>\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nHere is a portion of a housing development from Missoula, Montana. As part of her job, the development\u2019s lawn inspector has to walk down every street in the development making sure homeowners\u2019 landscaping conforms to the community requirements.\r\n\r\n<img class=\"alignnone size-full wp-image-134\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155110\/Fig2_5_1.png\" alt=\"Fig2_5_1\" width=\"574\" height=\"438\" \/>\r\n\r\nNaturally, she wants to minimize the amount of walking she has to do. Is it possible for her to walk down every street in this development without having to do any backtracking? While you might be able to answer that question just by looking at the picture for a while, it would be ideal to be able to answer the question for any picture regardless of its complexity.\r\n\r\nTo do that, we first need to simplify the picture into a form that is easier to work with. We can do that by drawing a simple line for each street. Where streets intersect, we will place a dot.\r\n\r\n<img class=\"aligncenter size-full wp-image-135\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155111\/Fig2_5_2.png\" alt=\"Fig2_5_2\" width=\"700\" height=\"264\" \/>\r\n\r\n<\/div>\r\nThis type of simplified picture is called a <strong>graph<\/strong>.\r\n<div class=\"textbox\">\r\n<h3>Graphs, Vertices, and Edges<\/h3>\r\nA <strong>graph<\/strong> consists of a set of dots, called <strong>vertices<\/strong>, and a set of <strong>edges<\/strong> connecting pairs of vertices.\r\n\r\n<\/div>\r\nWhile we drew our original graph to correspond with the picture we had, there is nothing particularly important about the layout when we analyze a graph. Both of the graphs below are equivalent to the one drawn above.\r\n\r\n<img class=\"aligncenter size-full wp-image-136\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155113\/Fig2_5_3.png\" alt=\"Fig2_5_3\" width=\"689\" height=\"266\" \/>\r\n\r\nYou probably already noticed that we are using the term<em> graph<\/em> differently than you may have used the term in the past to describe the graph of a mathematical function.\r\n\r\nWatch the video below to get another perspective of drawing a street network graph.\r\n\r\nhttps:\/\/youtu.be\/gyQhW24Dr2E\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\n<img class=\"alignright wp-image-137\" 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=\"Fig2_5_4\" width=\"300\" height=\"235\" \/>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 to the right.[footnote]Bogdan Giu\u015fc\u0103. http:\/\/en.wikipedia.org\/wiki\/File:Konigsberg_bridges.png[\/footnote]\r\n\r\nAs a weekend amusement, townsfolk would see if they could find a route that would take them across every bridge once and return them to where they started.\r\n\r\n<\/div>\r\nIn the following video we present another view of the K\u00f6nigsberg bridge problem.\r\n\r\nhttps:\/\/youtu.be\/yn-OD8OBSDM\r\n\r\nLeonard 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:\r\n\r\n<img class=\"alignnone 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=\"Fig2_5_5\" width=\"500\" height=\"193\" \/>\r\n\r\nSince 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:\r\n\r\n<img class=\"alignnone size-full wp-image-139\" 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=\"Fig2_5_6\" width=\"226\" height=\"199\" \/>\r\n\r\nNotice 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.\r\n\r\nWhile we haven\u2019t answered the actual question yet of whether or not there is a route which crosses every bridge once and returns to the starting location, the graph provides the foundation for exploring this question.\r\n<h3>Definitions<\/h3>\r\nWhile we loosely defined some terminology earlier, we now will try to be more specific.\r\n<div class=\"textbox\">\r\n<h3>Vertex<\/h3>\r\nA vertex is a dot in the graph that could represent an intersection of streets, a land mass, or a general location, like \u201cwork\u201d or \u201cschool\u201d. Vertices are often connected by edges. Note that vertices only occur when a dot is explicitly placed, not whenever two edges cross. Imagine a freeway overpass\u2014the freeway and side street cross, but it is not possible to change from the side street to the freeway at that point, so there is no intersection and no vertex would be placed.\r\n\r\n<\/div>\r\n<div class=\"textbox\">\r\n<h3>Edges<\/h3>\r\nEdges connect pairs of vertices. An edge can represent a physical connection between locations, like a street, or simply that a route connecting the two locations exists, like an airline flight.\r\n\r\n<\/div>\r\n<div class=\"textbox\">\r\n<h3>Loop<\/h3>\r\nA loop is a special type of edge that connects a vertex to itself. Loops are not used much in street network graphs.\r\n\r\n<img class=\"alignnone wp-image-140\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155118\/Fig2_5_7.png\" alt=\"Fig2_5_7\" width=\"245\" height=\"147\" \/>\r\n\r\n<\/div>\r\n<div class=\"textbox\">\r\n<h3>Degree of a vertex<\/h3>\r\nThe degree of a vertex is the number of edges meeting at that vertex. It is possible for a vertex to have a degree of zero or larger.\r\n<table>\r\n<thead>\r\n<tr>\r\n<th>Degree 0<\/th>\r\n<th>Degree 1<\/th>\r\n<th>Degree 2<\/th>\r\n<th>Degree 3<\/th>\r\n<th>Degree 4<\/th>\r\n<\/tr>\r\n<\/thead>\r\n<tbody>\r\n<tr>\r\n<td><img class=\"alignnone wp-image-141\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155119\/Fig2_5_8.png\" alt=\"Fig2_5_8\" width=\"30\" height=\"30\" \/><\/td>\r\n<td><img class=\"alignnone wp-image-142\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155119\/Fig2_5_9.png\" alt=\"Fig2_5_9\" width=\"90\" height=\"46\" \/><\/td>\r\n<td><img class=\"alignnone wp-image-143\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155120\/Fig2_5_10.png\" alt=\"Fig2_5_10\" width=\"140\" height=\"57\" \/><\/td>\r\n<td><img class=\"alignnone wp-image-144\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155120\/Fig2_5_11.png\" alt=\"Fig2_5_11\" width=\"140\" height=\"93\" \/><\/td>\r\n<td><img class=\"alignnone wp-image-145\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155121\/Fig2_5_12.png\" alt=\"Fig2_5_12\" width=\"140\" height=\"96\" \/><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<\/div>\r\n<div class=\"textbox\">\r\n<h3>Path<\/h3>\r\nA path is a sequence of vertices using the edges. Usually we are interested in a path between two vertices. For example, a path from vertex A to vertex M is shown below. It is one of many possible paths in this graph.\r\n\r\n<img class=\"alignnone wp-image-146\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155122\/Fig2_5_13.png\" alt=\"Fig2_5_13\" width=\"350\" height=\"148\" \/>\r\n\r\n<\/div>\r\n<div class=\"textbox\">\r\n<h3>Circuit<\/h3>\r\nA circuit is a path that begins and ends at the same vertex. A circuit starting and ending at vertex A is shown below.\r\n\r\n<img class=\"alignnone wp-image-147\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155123\/Fig2_5_14.png\" alt=\"Fig2_5_14\" width=\"350\" height=\"150\" \/>\r\n\r\n<\/div>\r\n<div class=\"textbox\">\r\n<h3>Connected<\/h3>\r\nA graph is connected if there is a path from any vertex to any other vertex. Every graph drawn so far has been connected. The graph below is <strong>disconnected<\/strong>; there is no way to get from the vertices on the left to the vertices on the right.\r\n\r\n<img class=\"alignnone wp-image-148\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155124\/Fig2_5_15.png\" alt=\"Fig2_5_15\" width=\"350\" height=\"137\" \/>\r\n\r\n<\/div>\r\n<div class=\"textbox\">\r\n<h3>Weights<\/h3>\r\nDepending upon the problem being solved, sometimes weights are assigned to the edges. The weights could represent the distance between two locations, the travel time, or the travel cost. It is important to note that the distance between vertices in a graph does not necessarily correspond to the weight of an edge.\r\n\r\n<\/div>\r\n&nbsp;\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try It Now<\/h3>\r\n1.The graph below shows 5 cities. The weights on the edges represent the airfare for a one -way flight between the cities.\r\na. How many vertices and edges does the graph have?\r\nb. Is the graph connected?\r\nc. What is the degree of the vertex representing LA?\r\nd. If you fly from Seattle to Dallas to Atlanta, is that a path or a circuit?\r\ne. If you fly from LA to Chicago to Dallas to LA, is that a path or a circuit.\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/01\/24020234\/Screen-Shot-2017-01-23-at-6.02.20-PM.png\"><img class=\" wp-image-1202 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/01\/24020234\/Screen-Shot-2017-01-23-at-6.02.20-PM-300x150.png\" alt=\"\" width=\"494\" height=\"247\" \/><\/a>\r\n<iframe id=\"mom5\" class=\"resizable\" src=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=6883&amp;theme=oea&amp;iframe_resize_id=mom5\" width=\"100%\" height=\"200\"><\/iframe>\r\n<iframe id=\"mom1\" class=\"resizable\" src=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=6885&amp;theme=oea&amp;iframe_resize_id=mom1\" width=\"100%\" height=\"500\"><\/iframe>\r\n\r\n<\/div>\r\n&nbsp;\r\n<h2>Shortest Path<\/h2>\r\nWhen you visit a website like Google Maps or use your Smartphone to ask for directions from home to your Aunt\u2019s house in Pasadena, you are usually looking for a shortest path between the two locations. These computer applications use representations of the street maps as graphs, with estimated driving times as edge weights.\r\n\r\nWhile often it is possible to find a shortest path on a small graph by guess-and-check, our goal in this chapter is to develop methods to solve complex problems in a systematic way by following <strong>algorithms<\/strong>. An algorithm is a step-by-step procedure for solving a problem. Dijkstra\u2019s (pronounced dike-stra) algorithm will find the shortest path between two vertices.\r\n\r\n&nbsp;\r\n<div class=\"textbox\">\r\n<div>\r\n<h3>Dijkstra\u2019s Algorithm<\/h3>\r\n<\/div>\r\n<div>\r\n\r\n1.\u00a0\u00a0\u00a0\u00a0 Mark the ending vertex with a distance of zero. Designate this vertex as current.\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0 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.\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0 Mark the current vertex as visited. We will never look at this vertex again.\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0 Mark the vertex with the smallest distance as current, and repeat from step 2.\r\n\r\n<\/div>\r\n&nbsp;\r\n\r\n<\/div>\r\n<div class=\"textbox exercises\">\r\n<h3>EXAMPLE<\/h3>\r\nSuppose you need to travel from Tacoma, WA (vertex T) to Yakima, WA (vertex Y). Looking at a map, it looks like driving through Auburn (A) then Mount Rainier (MR) might be shortest, but it\u2019s not totally clear since that road is probably slower than taking the major highway through North Bend (NB). A graph with travel times in minutes is shown below. An alternate route through Eatonville (E) and Packwood (P) is also shown.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16201559\/Untitled8.png\"><img class=\"wp-image-1840 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16201559\/Untitled8.png\" alt=\"Graph with 7 vertices and 8 edges. Refer to text for labels of vertices and edges\" width=\"428\" height=\"199\" \/><\/a>\r\n\r\nStep 1: Mark the ending vertex with a distance of zero. The distances will be recorded in [brackets] after the vertex name\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16201823\/Untitled9.png\"><img class=\" wp-image-1841 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16201823\/Untitled9.png\" alt=\"Same graph as above, with zero in brackets next to the Y vertex.\" width=\"374\" height=\"164\" \/><\/a>\r\n\r\nStep 2: For each vertex leading to Y, we calculate the distance to the end. For example, NB is a distance of 104 from the end, and MR is 96 from the end. Remember that distances in this case refer to the travel time in minutes.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16201934\/Untitled10.png\"><img class=\"aligncenter wp-image-1842\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16201934\/Untitled10.png\" alt=\"Same graph as above with [104] next to the NB vertex, [96] next to the MR vertex, [76] next to the P vertex.\" width=\"394\" height=\"174\" \/><\/a>\r\n<div>\r\n\r\nStep 3 &amp; 4: We mark Y as visited, and mark the vertex with the smallest recorded distance as current. At this point, P will be designated current. Back to step 2.\r\n<div>\r\n\r\nStep 2 (#2): For each vertex leading to P (and not leading to a visited vertex) we find the distance from the end. Since E is 96 minutes from P, and we\u2019ve already calculated P is 76 minutes from Y, we can compute that E is 96+76 = 172 minutes from Y.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16202207\/Untitled11.png\"><img class=\"alignnone wp-image-1843\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16202207\/Untitled11.png\" alt=\"Same graph as above with [172] next to the E vertex.\" width=\"495\" height=\"222\" \/><\/a>\r\n<div>\r\n\r\nStep 3 &amp; 4 (#2): We mark P as visited, and designate the vertex with the smallest recorded distance as current: MR. Back to step 2.\r\n<div>\r\n\r\nStep 2 (#3): For each vertex leading to MR (and not leading to a visited vertex) we find the distance to the end. The only vertex to be considered is A, since we\u2019ve already visited Y and P. Adding MR\u2019s distance 96 to the length from A to MR gives the distance 96+79 = 175 minutes from A to Y.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16202445\/Untitled12.png\"><img class=\" wp-image-1845 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16202445\/Untitled12.png\" alt=\"Same graph as above with [175] next to the vertex A.\" width=\"418\" height=\"186\" \/><\/a>\r\n<div>\r\n\r\nStep 3 &amp; 4 (#3): We mark MR as visited, and designate the vertex with smallest recorded distance as current: NB. Back to step 2.\r\n\r\nStep 2 (#4): \u00a0For each vertex leading to NB, we find the distance to the end. \u00a0We know the shortest distance from NB to Y is 104 and the distance from A to NB is 36, so the distance from A to Y through NB is 104+36 = 140. \u00a0Since this distance is shorter than the previously calculated distance from Y to A through MR, we replace it.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16203219\/Untitled13.png\"><img class=\"wp-image-1846 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16203219\/Untitled13.png\" alt=\"Same graph as above with MR and P crossed out\" width=\"403\" height=\"181\" \/><\/a>\r\n\r\nStep 3 &amp; 4 (#4): We mark NB as visited, and designate A as current, since it now has the shortest distance.\r\n<div>\r\n\r\nStep 2 (#5): T is the only non-visited vertex leading to A, so we calculate the distance from T to Y through A: 20+140 = 160 minutes.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16203331\/Untitled14.png\"><img class=\" wp-image-1847 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16203331\/Untitled14.png\" alt=\"Same graph as above with NB crossed out\" width=\"419\" height=\"173\" \/><\/a>\r\n<div>\r\n\r\nStep 3 &amp; 4 (#5): We mark A as visited, and designate E as current.\r\n\r\n&nbsp;\r\n\r\nStep 2 (#6): The only non-visited vertex leading to E is T. Calculating the distance from T to Y through E, we compute 172+57 = 229 minutes. Since this is longer than the existing marked time, we do not replace it.\r\n\r\n&nbsp;\r\n\r\nStep 3 (#6): We mark E as visited. Since all vertices have been visited, we are done.\r\n\r\n&nbsp;\r\n\r\nFrom this, we know that the shortest path from Tacoma to Yakima will take 160 minutes. Tracking which sequence of edges yielded 160 minutes, we see the shortest path is T-A-NB-Y.\r\n\r\nDijkstra\u2019s algorithm is an <strong>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 <strong>efficient<\/strong>, meaning that it can be implemented in a reasonable amount of time. Dijkstra\u2019s algorithm takes around V2 calculations, where V is the number of vertices in a graph<a href=\"#_ftn1\">[1]<\/a>. A graph with 100 vertices would take around 10,000 calculations. While that would be a lot to do by hand, it is not a lot for computer to handle. It is because of this efficiency that your car\u2019s GPS unit can compute driving directions in only a few seconds.\r\n<div>\r\n\r\n<a href=\"#_ftnref1\">[1]<\/a> It can be made to run faster through various optimizations to the implementation.\r\n\r\nIn contrast, an <strong>inefficient<\/strong> algorithm might try to list all possible paths then compute the length of each path. Trying to list all possible paths could easily take 1025 calculations to compute the shortest path with only 25 vertices; that\u2019s a 1 with 25 zeros after it! To put that in perspective, the fastest computer in the world would still spend over 1000 years analyzing all those paths.\r\n\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n&nbsp;\r\n<div class=\"textbox exercises\">\r\n<h3>EXAMPLE<\/h3>\r\nA 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.\r\n\r\nThe 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<table>\r\n<tbody>\r\n<tr>\r\n<td><\/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><\/td>\r\n<td><\/td>\r\n<td>15<\/td>\r\n<td>14<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Denver<\/td>\r\n<td><\/td>\r\n<td>*<\/td>\r\n<td><\/td>\r\n<td>18<\/td>\r\n<td>24<\/td>\r\n<td>19<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Dallas<\/td>\r\n<td><\/td>\r\n<td><\/td>\r\n<td>*<\/td>\r\n<td>18<\/td>\r\n<td>15<\/td>\r\n<td>25<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Chicago<\/td>\r\n<td>15<\/td>\r\n<td>18<\/td>\r\n<td>18<\/td>\r\n<td>*<\/td>\r\n<td>14<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Atlanta<\/td>\r\n<td>14<\/td>\r\n<td>24<\/td>\r\n<td>15<\/td>\r\n<td>14<\/td>\r\n<td>*<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Bakersfield<\/td>\r\n<td><\/td>\r\n<td>19<\/td>\r\n<td>25<\/td>\r\n<td><\/td>\r\n<td><\/td>\r\n<td>*<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<div>\r\n\r\nWhile we could draw a graph, we can also work directly from the table.\r\n\r\nStep 1: The ending vertex, Bakersfield, is marked as current.\r\n\r\nStep 2: All cities connected to Bakersfield, in this case Denver and Dallas, have their distances calculated; we\u2019ll mark those distances in the column headers.\r\n\r\n<\/div>\r\nStep 3 &amp; 4: Mark Bakersfield as visited. 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.\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><\/td>\r\n<td>Baltimore\r\n\r\n&nbsp;<\/td>\r\n<td><strong>Denver<\/strong>\r\n\r\n[19]<\/td>\r\n<td>Dallas\r\n\r\n[25]<\/td>\r\n<td>Chicago<\/td>\r\n<td>Atlanta<\/td>\r\n<td>Bakersfield\r\n\r\n[0]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Baltimore<\/td>\r\n<td>*<\/td>\r\n<td><\/td>\r\n<td><\/td>\r\n<td>15<\/td>\r\n<td>14<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr>\r\n<td><strong>Denver<\/strong><\/td>\r\n<td><\/td>\r\n<td>*<\/td>\r\n<td><\/td>\r\n<td>18<\/td>\r\n<td>24<\/td>\r\n<td>19<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Dallas<\/td>\r\n<td><\/td>\r\n<td><\/td>\r\n<td>*<\/td>\r\n<td>18<\/td>\r\n<td>15<\/td>\r\n<td>25<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Chicago<\/td>\r\n<td>15<\/td>\r\n<td>18<\/td>\r\n<td>18<\/td>\r\n<td>*<\/td>\r\n<td>14<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Atlanta<\/td>\r\n<td>14<\/td>\r\n<td>24<\/td>\r\n<td>15<\/td>\r\n<td>14<\/td>\r\n<td>*<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Bakersfield<\/td>\r\n<td><\/td>\r\n<td>19<\/td>\r\n<td>25<\/td>\r\n<td><\/td>\r\n<td><\/td>\r\n<td>*<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<div>\r\n\r\nStep 2 (#2): For cities connected to Denver, calculate distance to the end. For example, Chicago is 18 hours from Denver, and Denver is 19 hours from the end, the distance for Chicago to the end is 18+19 = 37 (Chicago to Denver to Bakersfield). Atlanta is 24 hours from Denver, so the distance to the end is 24+19 = 43 (Atlanta to Denver to Bakersfield).\r\n\r\nStep 3 &amp; 4 (#2): We mark Denver as visited and mark Dallas as current.\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><\/td>\r\n<td>Baltimore\r\n\r\n&nbsp;<\/td>\r\n<td>Denver\r\n\r\n[19]<\/td>\r\n<td><strong>Dallas<\/strong>\r\n\r\n[25]<\/td>\r\n<td>Chicago\r\n\r\n[37]<\/td>\r\n<td>Atlanta\r\n\r\n[43]<\/td>\r\n<td>Bakersfield\r\n\r\n[0]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Baltimore<\/td>\r\n<td>*<\/td>\r\n<td><\/td>\r\n<td><\/td>\r\n<td>15<\/td>\r\n<td>14<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Denver<\/td>\r\n<td><\/td>\r\n<td>*<\/td>\r\n<td><\/td>\r\n<td>18<\/td>\r\n<td>24<\/td>\r\n<td>19<\/td>\r\n<\/tr>\r\n<tr>\r\n<td><strong>Dallas<\/strong><\/td>\r\n<td><\/td>\r\n<td><\/td>\r\n<td>*<\/td>\r\n<td>18<\/td>\r\n<td>15<\/td>\r\n<td>25<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Chicago<\/td>\r\n<td>15<\/td>\r\n<td>18<\/td>\r\n<td>18<\/td>\r\n<td>*<\/td>\r\n<td>14<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Atlanta<\/td>\r\n<td>14<\/td>\r\n<td>24<\/td>\r\n<td>15<\/td>\r\n<td>14<\/td>\r\n<td>*<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Bakersfield<\/td>\r\n<td><\/td>\r\n<td>19<\/td>\r\n<td>25<\/td>\r\n<td><\/td>\r\n<td><\/td>\r\n<td>*<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<div>\r\n\r\nStep 2 (#3): For cities connected to Dallas, calculate the distance to the end. For Chicago, the distance from Chicago to Dallas is 18 and from Dallas to the end is 25, so the distance from Chicago to the end through Dallas would be 18+25 = 43. Since this is longer than the currently marked distance for Chicago, we do not replace it. For Atlanta, we calculate 15+25 = 40. Since this is shorter than the currently marked distance for Atlanta, we replace the existing distance.\r\n\r\nStep 3 &amp; 4 (#3): We mark Dallas as visited, and mark Chicago as current.\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><\/td>\r\n<td>Baltimore\r\n\r\n&nbsp;<\/td>\r\n<td>Denver\r\n\r\n[19]<\/td>\r\n<td>Dallas\r\n\r\n[25]<\/td>\r\n<td><strong>Chicago<\/strong>\r\n\r\n[37]<\/td>\r\n<td>Atlanta\r\n\r\n[40]<\/td>\r\n<td>Bakersfield\r\n\r\n[0]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Baltimore<\/td>\r\n<td>*<\/td>\r\n<td><\/td>\r\n<td><\/td>\r\n<td>15<\/td>\r\n<td>14<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Denver<\/td>\r\n<td><\/td>\r\n<td>*<\/td>\r\n<td><\/td>\r\n<td>18<\/td>\r\n<td>24<\/td>\r\n<td>19<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Dallas<\/td>\r\n<td><\/td>\r\n<td><\/td>\r\n<td>*<\/td>\r\n<td>18<\/td>\r\n<td>15<\/td>\r\n<td>25<\/td>\r\n<\/tr>\r\n<tr>\r\n<td><strong>Chicago<\/strong><\/td>\r\n<td>15<\/td>\r\n<td>18<\/td>\r\n<td>18<\/td>\r\n<td>*<\/td>\r\n<td>14<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Atlanta<\/td>\r\n<td>14<\/td>\r\n<td>24<\/td>\r\n<td>15<\/td>\r\n<td>14<\/td>\r\n<td>*<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Bakersfield<\/td>\r\n<td><\/td>\r\n<td>19<\/td>\r\n<td>25<\/td>\r\n<td><\/td>\r\n<td><\/td>\r\n<td>*<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<div>\r\n\r\nStep 2 (#4): Baltimore and Atlanta are the only non-visited cities connected to Chicago. For Baltimore, we calculate 15+37 = 52 and mark that distance. For Atlanta, we calculate 14+37 = 51. Since this is longer than the existing distance of 40 for Atlanta, we do not replace that distance.\r\n\r\nStep 3 &amp; 4 (#4): Mark Chicago as visited and Atlanta as current.\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><\/td>\r\n<td>Baltimore\r\n\r\n[52]<\/td>\r\n<td>Denver\r\n\r\n[19]<\/td>\r\n<td>Dallas\r\n\r\n[25]<\/td>\r\n<td>Chicago\r\n\r\n[37]<\/td>\r\n<td><strong>Atlanta<\/strong>\r\n\r\n[40]<\/td>\r\n<td>Bakersfield\r\n\r\n[0]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Baltimore<\/td>\r\n<td>*<\/td>\r\n<td><\/td>\r\n<td><\/td>\r\n<td>15<\/td>\r\n<td>14<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Denver<\/td>\r\n<td><\/td>\r\n<td>*<\/td>\r\n<td><\/td>\r\n<td>18<\/td>\r\n<td>24<\/td>\r\n<td>19<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Dallas<\/td>\r\n<td><\/td>\r\n<td><\/td>\r\n<td>*<\/td>\r\n<td>18<\/td>\r\n<td>15<\/td>\r\n<td>25<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Chicago<\/td>\r\n<td>15<\/td>\r\n<td>18<\/td>\r\n<td>18<\/td>\r\n<td>*<\/td>\r\n<td>14<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr>\r\n<td><strong>Atlanta<\/strong><\/td>\r\n<td>14<\/td>\r\n<td>24<\/td>\r\n<td>15<\/td>\r\n<td>14<\/td>\r\n<td>*<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Bakersfield<\/td>\r\n<td><\/td>\r\n<td>19<\/td>\r\n<td>25<\/td>\r\n<td><\/td>\r\n<td><\/td>\r\n<td>*<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<div>\r\n\r\nStep 2 (#5): The distance from Atlanta to Baltimore is 14. Adding that to the distance already calculated for Atlanta gives a total distance of 14+40 = 54 hours from Baltimore to Bakersfield through Atlanta. Since this is larger than the currently calculated distance, we do not replace the distance for Baltimore.\r\n\r\nStep 3 &amp; 4 (#5): We mark Atlanta as visited. All cities have been visited and we are done.\r\n\r\nThe shortest route from Baltimore to Bakersfield will take 52 hours, and will route through Chicago and Denver.\r\n\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n&nbsp;\r\n<div class=\"textbox key-takeaways\">\r\n<h3>TRY IT NOW<\/h3>\r\n<div>\r\n<ul>\r\n \t<li>Find the shortest path between vertices A and G in the graph below.<\/li>\r\n<\/ul>\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16203716\/Untitled16.png\"><img class=\" wp-image-1848 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16203716\/Untitled16.png\" alt=\"Graph with 7 vertices labeled A, B, C, D, E, F, G. Edge between A, B is labeled 1, edge between A, C is 4, edge between B, E is 6, edge between E, G is 7, edge between G, F is 6, edge between f, c is 5, edge between c, a is 4, edge between c, d is 2, edge between b, d is 3 edge between e, d is 2, edge between e, f is 2, edge between f, d is 4. \" width=\"410\" height=\"236\" \/><\/a>\r\n\r\n<iframe id=\"mom5\" class=\"resizable\" src=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=6888&amp;theme=oea&amp;iframe_resize_id=mom5\" width=\"100%\" height=\"500\"><\/iframe>\r\n\r\n<\/div>\r\nThe following video summarizes the topics covered on this page.\r\n\r\nhttps:\/\/youtu.be\/KvRwplnIoEM\r\n\r\n<\/div>","rendered":"<p>In this lesson, we will introduce Graph Theory, a field of mathematics that started approximately 300 years ago to help solve problems such as finding the shortest path between two locations.<\/p>\n<p>Now, elements of graph theory are used to optimize a wide range of\u00a0systems, generate friend suggestions on social media, and plan complex shipping and air traffic routes.<\/p>\n<div class=\"textbox learning-objectives\">\n<h3>Learning Objectives<\/h3>\n<p>In this lesson you will learn how to:<\/p>\n<ul>\n<li>Identify the vertices, edges, and loops of a graph<\/li>\n<li>Identify the degree of a vertex<\/li>\n<li>Identify and draw 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<\/div>\n<h2>Elements of Graph Theory<\/h2>\n<p>In the modern world, planning efficient routes is essential for business and industry, with applications as varied as product distribution, laying new fiber optic lines for broadband internet, and suggesting new friends within social network websites like Facebook.<\/p>\n<p>This field of mathematics started nearly 300 years ago as a look into a mathematical puzzle (we\u2019ll look at it in a bit). The field has exploded in importance in the last century, both because of the growing complexity of business in a global economy and because of the computational power that computers have provided us.<\/p>\n<h3>Drawing Graphs<\/h3>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>Here is a portion of a housing development from Missoula, Montana. As part of her job, the development\u2019s lawn inspector has to walk down every street in the development making sure homeowners\u2019 landscaping conforms to the community requirements.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-134\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155110\/Fig2_5_1.png\" alt=\"Fig2_5_1\" width=\"574\" height=\"438\" \/><\/p>\n<p>Naturally, she wants to minimize the amount of walking she has to do. Is it possible for her to walk down every street in this development without having to do any backtracking? While you might be able to answer that question just by looking at the picture for a while, it would be ideal to be able to answer the question for any picture regardless of its complexity.<\/p>\n<p>To do that, we first need to simplify the picture into a form that is easier to work with. We can do that by drawing a simple line for each street. Where streets intersect, we will place a dot.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-135\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155111\/Fig2_5_2.png\" alt=\"Fig2_5_2\" width=\"700\" height=\"264\" \/><\/p>\n<\/div>\n<p>This type of simplified picture is called a <strong>graph<\/strong>.<\/p>\n<div class=\"textbox\">\n<h3>Graphs, Vertices, and Edges<\/h3>\n<p>A <strong>graph<\/strong> consists of a set of dots, called <strong>vertices<\/strong>, and a set of <strong>edges<\/strong> connecting pairs of vertices.<\/p>\n<\/div>\n<p>While we drew our original graph to correspond with the picture we had, there is nothing particularly important about the layout when we analyze a graph. Both of the graphs below are equivalent to the one drawn above.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-136\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155113\/Fig2_5_3.png\" alt=\"Fig2_5_3\" width=\"689\" height=\"266\" \/><\/p>\n<p>You probably already noticed that we are using the term<em> graph<\/em> differently than you may have used the term in the past to describe the graph of a mathematical function.<\/p>\n<p>Watch the video below to get another perspective of drawing a street network graph.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-1\" title=\"Drawing a street network graph\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/gyQhW24Dr2E?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignright wp-image-137\" 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=\"Fig2_5_4\" width=\"300\" height=\"235\" \/>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 to the right.<a class=\"footnote\" title=\"Bogdan Giu\u015fc\u0103. http:\/\/en.wikipedia.org\/wiki\/File:Konigsberg_bridges.png\" id=\"return-footnote-206-1\" href=\"#footnote-206-1\" aria-label=\"Footnote 1\"><sup class=\"footnote\">[1]<\/sup><\/a><\/p>\n<p>As a weekend amusement, townsfolk would see if they could find a route that would take them across every bridge once and return them to where they started.<\/p>\n<\/div>\n<p>In the following video we present another view of the K\u00f6nigsberg bridge problem.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-2\" title=\"Drawing a graph for bridges\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/yn-OD8OBSDM?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\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<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone 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=\"Fig2_5_5\" width=\"500\" height=\"193\" \/><\/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<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-139\" 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=\"Fig2_5_6\" width=\"226\" height=\"199\" \/><\/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 which crosses every bridge once and returns to the starting location, the graph provides the foundation for exploring this question.<\/p>\n<h3>Definitions<\/h3>\n<p>While we loosely defined some terminology earlier, we now will try to be more specific.<\/p>\n<div class=\"textbox\">\n<h3>Vertex<\/h3>\n<p>A vertex is a dot in the graph that could represent an intersection of streets, a land mass, or a general location, like \u201cwork\u201d or \u201cschool\u201d. Vertices are often connected by edges. Note that vertices only occur when a dot is explicitly placed, not whenever two edges cross. Imagine a freeway overpass\u2014the freeway and side street cross, but it is not possible to change from the side street to the freeway at that point, so there is no intersection and no vertex would be placed.<\/p>\n<\/div>\n<div class=\"textbox\">\n<h3>Edges<\/h3>\n<p>Edges connect pairs of vertices. An edge can represent a physical connection between locations, like a street, or simply that a route connecting the two locations exists, like an airline flight.<\/p>\n<\/div>\n<div class=\"textbox\">\n<h3>Loop<\/h3>\n<p>A loop is a special type of edge that connects a vertex to itself. Loops are not used much in street network graphs.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-140\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155118\/Fig2_5_7.png\" alt=\"Fig2_5_7\" width=\"245\" height=\"147\" \/><\/p>\n<\/div>\n<div class=\"textbox\">\n<h3>Degree of a vertex<\/h3>\n<p>The degree of a vertex is the number of edges meeting at that vertex. It is possible for a vertex to have a degree of zero or larger.<\/p>\n<table>\n<thead>\n<tr>\n<th>Degree 0<\/th>\n<th>Degree 1<\/th>\n<th>Degree 2<\/th>\n<th>Degree 3<\/th>\n<th>Degree 4<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-141\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155119\/Fig2_5_8.png\" alt=\"Fig2_5_8\" width=\"30\" height=\"30\" \/><\/td>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-142\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155119\/Fig2_5_9.png\" alt=\"Fig2_5_9\" width=\"90\" height=\"46\" \/><\/td>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-143\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155120\/Fig2_5_10.png\" alt=\"Fig2_5_10\" width=\"140\" height=\"57\" \/><\/td>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-144\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155120\/Fig2_5_11.png\" alt=\"Fig2_5_11\" width=\"140\" height=\"93\" \/><\/td>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-145\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155121\/Fig2_5_12.png\" alt=\"Fig2_5_12\" width=\"140\" height=\"96\" \/><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<div class=\"textbox\">\n<h3>Path<\/h3>\n<p>A path is a sequence of vertices using the edges. Usually we are interested in a path between two vertices. For example, a path from vertex A to vertex M is shown below. It is one of many possible paths in this graph.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-146\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155122\/Fig2_5_13.png\" alt=\"Fig2_5_13\" width=\"350\" height=\"148\" \/><\/p>\n<\/div>\n<div class=\"textbox\">\n<h3>Circuit<\/h3>\n<p>A circuit is a path that begins and ends at the same vertex. A circuit starting and ending at vertex A is shown below.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-147\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155123\/Fig2_5_14.png\" alt=\"Fig2_5_14\" width=\"350\" height=\"150\" \/><\/p>\n<\/div>\n<div class=\"textbox\">\n<h3>Connected<\/h3>\n<p>A graph is connected if there is a path from any vertex to any other vertex. Every graph drawn so far has been connected. The graph below is <strong>disconnected<\/strong>; there is no way to get from the vertices on the left to the vertices on the right.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-148\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155124\/Fig2_5_15.png\" alt=\"Fig2_5_15\" width=\"350\" height=\"137\" \/><\/p>\n<\/div>\n<div class=\"textbox\">\n<h3>Weights<\/h3>\n<p>Depending upon the problem being solved, sometimes weights are assigned to the edges. The weights could represent the distance between two locations, the travel time, or the travel cost. It is important to note that the distance between vertices in a graph does not necessarily correspond to the weight of an edge.<\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<div class=\"textbox key-takeaways\">\n<h3>Try It Now<\/h3>\n<p>1.The graph below shows 5 cities. The weights on the edges represent the airfare for a one -way flight between the cities.<br \/>\na. How many vertices and edges does the graph have?<br \/>\nb. Is the graph connected?<br \/>\nc. What is the degree of the vertex representing LA?<br \/>\nd. If you fly from Seattle to Dallas to Atlanta, is that a path or a circuit?<br \/>\ne. If you fly from LA to Chicago to Dallas to LA, is that a path or a circuit.<br \/>\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/01\/24020234\/Screen-Shot-2017-01-23-at-6.02.20-PM.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1202 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/01\/24020234\/Screen-Shot-2017-01-23-at-6.02.20-PM-300x150.png\" alt=\"\" width=\"494\" height=\"247\" \/><\/a><br \/>\n<iframe loading=\"lazy\" id=\"mom5\" class=\"resizable\" src=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=6883&amp;theme=oea&amp;iframe_resize_id=mom5\" width=\"100%\" height=\"200\"><\/iframe><br \/>\n<iframe loading=\"lazy\" id=\"mom1\" class=\"resizable\" src=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=6885&amp;theme=oea&amp;iframe_resize_id=mom1\" width=\"100%\" height=\"500\"><\/iframe><\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<h2>Shortest Path<\/h2>\n<p>When you visit a website like Google Maps or use your Smartphone to ask for directions from home to your Aunt\u2019s house in Pasadena, you are usually looking for a shortest path between the two locations. These computer applications use representations of the street maps as graphs, with estimated driving times as edge weights.<\/p>\n<p>While often it is possible to find a shortest path on a small graph by guess-and-check, our goal in this chapter is to develop methods to solve complex problems in a systematic way by following <strong>algorithms<\/strong>. An algorithm is a step-by-step procedure for solving a problem. Dijkstra\u2019s (pronounced dike-stra) algorithm will find the shortest path between two vertices.<\/p>\n<p>&nbsp;<\/p>\n<div class=\"textbox\">\n<div>\n<h3>Dijkstra\u2019s Algorithm<\/h3>\n<\/div>\n<div>\n<p>1.\u00a0\u00a0\u00a0\u00a0 Mark the ending vertex with a distance of zero. Designate this vertex as current.<\/p>\n<p>2.\u00a0\u00a0\u00a0\u00a0 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.<\/p>\n<p>3.\u00a0\u00a0\u00a0\u00a0 Mark the current vertex as visited. We will never look at this vertex again.<\/p>\n<p>4.\u00a0\u00a0\u00a0\u00a0 Mark the vertex with the smallest distance as current, and repeat from step 2.<\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<\/div>\n<div class=\"textbox exercises\">\n<h3>EXAMPLE<\/h3>\n<p>Suppose you need to travel from Tacoma, WA (vertex T) to Yakima, WA (vertex Y). Looking at a map, it looks like driving through Auburn (A) then Mount Rainier (MR) might be shortest, but it\u2019s not totally clear since that road is probably slower than taking the major highway through North Bend (NB). A graph with travel times in minutes is shown below. An alternate route through Eatonville (E) and Packwood (P) is also shown.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16201559\/Untitled8.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1840 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16201559\/Untitled8.png\" alt=\"Graph with 7 vertices and 8 edges. Refer to text for labels of vertices and edges\" width=\"428\" height=\"199\" \/><\/a><\/p>\n<p>Step 1: Mark the ending vertex with a distance of zero. The distances will be recorded in [brackets] after the vertex name<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16201823\/Untitled9.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1841 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16201823\/Untitled9.png\" alt=\"Same graph as above, with zero in brackets next to the Y vertex.\" width=\"374\" height=\"164\" \/><\/a><\/p>\n<p>Step 2: For each vertex leading to Y, we calculate the distance to the end. For example, NB is a distance of 104 from the end, and MR is 96 from the end. Remember that distances in this case refer to the travel time in minutes.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16201934\/Untitled10.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-1842\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16201934\/Untitled10.png\" alt=\"Same graph as above with [104] next to the NB vertex, [96] next to the MR vertex, [76] next to the P vertex.\" width=\"394\" height=\"174\" \/><\/a><\/p>\n<div>\n<p>Step 3 &amp; 4: We mark Y as visited, and mark the vertex with the smallest recorded distance as current. At this point, P will be designated current. Back to step 2.<\/p>\n<div>\n<p>Step 2 (#2): For each vertex leading to P (and not leading to a visited vertex) we find the distance from the end. Since E is 96 minutes from P, and we\u2019ve already calculated P is 76 minutes from Y, we can compute that E is 96+76 = 172 minutes from Y.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16202207\/Untitled11.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-1843\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16202207\/Untitled11.png\" alt=\"Same graph as above with [172] next to the E vertex.\" width=\"495\" height=\"222\" \/><\/a><\/p>\n<div>\n<p>Step 3 &amp; 4 (#2): We mark P as visited, and designate the vertex with the smallest recorded distance as current: MR. Back to step 2.<\/p>\n<div>\n<p>Step 2 (#3): For each vertex leading to MR (and not leading to a visited vertex) we find the distance to the end. The only vertex to be considered is A, since we\u2019ve already visited Y and P. Adding MR\u2019s distance 96 to the length from A to MR gives the distance 96+79 = 175 minutes from A to Y.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16202445\/Untitled12.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1845 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16202445\/Untitled12.png\" alt=\"Same graph as above with [175] next to the vertex A.\" width=\"418\" height=\"186\" \/><\/a><\/p>\n<div>\n<p>Step 3 &amp; 4 (#3): We mark MR as visited, and designate the vertex with smallest recorded distance as current: NB. Back to step 2.<\/p>\n<p>Step 2 (#4): \u00a0For each vertex leading to NB, we find the distance to the end. \u00a0We know the shortest distance from NB to Y is 104 and the distance from A to NB is 36, so the distance from A to Y through NB is 104+36 = 140. \u00a0Since this distance is shorter than the previously calculated distance from Y to A through MR, we replace it.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16203219\/Untitled13.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1846 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16203219\/Untitled13.png\" alt=\"Same graph as above with MR and P crossed out\" width=\"403\" height=\"181\" \/><\/a><\/p>\n<p>Step 3 &amp; 4 (#4): We mark NB as visited, and designate A as current, since it now has the shortest distance.<\/p>\n<div>\n<p>Step 2 (#5): T is the only non-visited vertex leading to A, so we calculate the distance from T to Y through A: 20+140 = 160 minutes.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16203331\/Untitled14.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1847 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16203331\/Untitled14.png\" alt=\"Same graph as above with NB crossed out\" width=\"419\" height=\"173\" \/><\/a><\/p>\n<div>\n<p>Step 3 &amp; 4 (#5): We mark A as visited, and designate E as current.<\/p>\n<p>&nbsp;<\/p>\n<p>Step 2 (#6): The only non-visited vertex leading to E is T. Calculating the distance from T to Y through E, we compute 172+57 = 229 minutes. Since this is longer than the existing marked time, we do not replace it.<\/p>\n<p>&nbsp;<\/p>\n<p>Step 3 (#6): We mark E as visited. Since all vertices have been visited, we are done.<\/p>\n<p>&nbsp;<\/p>\n<p>From this, we know that the shortest path from Tacoma to Yakima will take 160 minutes. Tracking which sequence of edges yielded 160 minutes, we see the shortest path is T-A-NB-Y.<\/p>\n<p>Dijkstra\u2019s algorithm is an <strong>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 <strong>efficient<\/strong>, meaning that it can be implemented in a reasonable amount of time. Dijkstra\u2019s algorithm takes around V2 calculations, where V is the number of vertices in a graph<a href=\"#_ftn1\">[1]<\/a>. A graph with 100 vertices would take around 10,000 calculations. While that would be a lot to do by hand, it is not a lot for computer to handle. It is because of this efficiency that your car\u2019s GPS unit can compute driving directions in only a few seconds.<\/p>\n<div>\n<p><a href=\"#_ftnref1\">[1]<\/a> It can be made to run faster through various optimizations to the implementation.<\/p>\n<p>In contrast, an <strong>inefficient<\/strong> algorithm might try to list all possible paths then compute the length of each path. Trying to list all possible paths could easily take 1025 calculations to compute the shortest path with only 25 vertices; that\u2019s a 1 with 25 zeros after it! To put that in perspective, the fastest computer in the world would still spend over 1000 years analyzing all those paths.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<p>&nbsp;<\/p>\n<div class=\"textbox exercises\">\n<h3>EXAMPLE<\/h3>\n<p>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.<\/p>\n<p>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><\/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><\/td>\n<td><\/td>\n<td>15<\/td>\n<td>14<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>Denver<\/td>\n<td><\/td>\n<td>*<\/td>\n<td><\/td>\n<td>18<\/td>\n<td>24<\/td>\n<td>19<\/td>\n<\/tr>\n<tr>\n<td>Dallas<\/td>\n<td><\/td>\n<td><\/td>\n<td>*<\/td>\n<td>18<\/td>\n<td>15<\/td>\n<td>25<\/td>\n<\/tr>\n<tr>\n<td>Chicago<\/td>\n<td>15<\/td>\n<td>18<\/td>\n<td>18<\/td>\n<td>*<\/td>\n<td>14<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>Atlanta<\/td>\n<td>14<\/td>\n<td>24<\/td>\n<td>15<\/td>\n<td>14<\/td>\n<td>*<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>Bakersfield<\/td>\n<td><\/td>\n<td>19<\/td>\n<td>25<\/td>\n<td><\/td>\n<td><\/td>\n<td>*<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div>\n<p>While we could draw a graph, we can also work directly from the table.<\/p>\n<p>Step 1: The ending vertex, Bakersfield, is marked as current.<\/p>\n<p>Step 2: All cities connected to Bakersfield, in this case Denver and Dallas, have their distances calculated; we\u2019ll mark those distances in the column headers.<\/p>\n<\/div>\n<p>Step 3 &amp; 4: Mark Bakersfield as visited. 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><\/td>\n<td>Baltimore<\/p>\n<p>&nbsp;<\/td>\n<td><strong>Denver<\/strong><\/p>\n<p>[19]<\/td>\n<td>Dallas<\/p>\n<p>[25]<\/td>\n<td>Chicago<\/td>\n<td>Atlanta<\/td>\n<td>Bakersfield<\/p>\n<p>[0]<\/td>\n<\/tr>\n<tr>\n<td>Baltimore<\/td>\n<td>*<\/td>\n<td><\/td>\n<td><\/td>\n<td>15<\/td>\n<td>14<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td><strong>Denver<\/strong><\/td>\n<td><\/td>\n<td>*<\/td>\n<td><\/td>\n<td>18<\/td>\n<td>24<\/td>\n<td>19<\/td>\n<\/tr>\n<tr>\n<td>Dallas<\/td>\n<td><\/td>\n<td><\/td>\n<td>*<\/td>\n<td>18<\/td>\n<td>15<\/td>\n<td>25<\/td>\n<\/tr>\n<tr>\n<td>Chicago<\/td>\n<td>15<\/td>\n<td>18<\/td>\n<td>18<\/td>\n<td>*<\/td>\n<td>14<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>Atlanta<\/td>\n<td>14<\/td>\n<td>24<\/td>\n<td>15<\/td>\n<td>14<\/td>\n<td>*<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>Bakersfield<\/td>\n<td><\/td>\n<td>19<\/td>\n<td>25<\/td>\n<td><\/td>\n<td><\/td>\n<td>*<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div>\n<p>Step 2 (#2): For cities connected to Denver, calculate distance to the end. For example, Chicago is 18 hours from Denver, and Denver is 19 hours from the end, the distance for Chicago to the end is 18+19 = 37 (Chicago to Denver to Bakersfield). Atlanta is 24 hours from Denver, so the distance to the end is 24+19 = 43 (Atlanta to Denver to Bakersfield).<\/p>\n<p>Step 3 &amp; 4 (#2): We mark Denver as visited and mark Dallas as current.<\/p>\n<table>\n<tbody>\n<tr>\n<td><\/td>\n<td>Baltimore<\/p>\n<p>&nbsp;<\/td>\n<td>Denver<\/p>\n<p>[19]<\/td>\n<td><strong>Dallas<\/strong><\/p>\n<p>[25]<\/td>\n<td>Chicago<\/p>\n<p>[37]<\/td>\n<td>Atlanta<\/p>\n<p>[43]<\/td>\n<td>Bakersfield<\/p>\n<p>[0]<\/td>\n<\/tr>\n<tr>\n<td>Baltimore<\/td>\n<td>*<\/td>\n<td><\/td>\n<td><\/td>\n<td>15<\/td>\n<td>14<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>Denver<\/td>\n<td><\/td>\n<td>*<\/td>\n<td><\/td>\n<td>18<\/td>\n<td>24<\/td>\n<td>19<\/td>\n<\/tr>\n<tr>\n<td><strong>Dallas<\/strong><\/td>\n<td><\/td>\n<td><\/td>\n<td>*<\/td>\n<td>18<\/td>\n<td>15<\/td>\n<td>25<\/td>\n<\/tr>\n<tr>\n<td>Chicago<\/td>\n<td>15<\/td>\n<td>18<\/td>\n<td>18<\/td>\n<td>*<\/td>\n<td>14<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>Atlanta<\/td>\n<td>14<\/td>\n<td>24<\/td>\n<td>15<\/td>\n<td>14<\/td>\n<td>*<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>Bakersfield<\/td>\n<td><\/td>\n<td>19<\/td>\n<td>25<\/td>\n<td><\/td>\n<td><\/td>\n<td>*<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div>\n<p>Step 2 (#3): For cities connected to Dallas, calculate the distance to the end. For Chicago, the distance from Chicago to Dallas is 18 and from Dallas to the end is 25, so the distance from Chicago to the end through Dallas would be 18+25 = 43. Since this is longer than the currently marked distance for Chicago, we do not replace it. For Atlanta, we calculate 15+25 = 40. Since this is shorter than the currently marked distance for Atlanta, we replace the existing distance.<\/p>\n<p>Step 3 &amp; 4 (#3): We mark Dallas as visited, and mark Chicago as current.<\/p>\n<table>\n<tbody>\n<tr>\n<td><\/td>\n<td>Baltimore<\/p>\n<p>&nbsp;<\/td>\n<td>Denver<\/p>\n<p>[19]<\/td>\n<td>Dallas<\/p>\n<p>[25]<\/td>\n<td><strong>Chicago<\/strong><\/p>\n<p>[37]<\/td>\n<td>Atlanta<\/p>\n<p>[40]<\/td>\n<td>Bakersfield<\/p>\n<p>[0]<\/td>\n<\/tr>\n<tr>\n<td>Baltimore<\/td>\n<td>*<\/td>\n<td><\/td>\n<td><\/td>\n<td>15<\/td>\n<td>14<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>Denver<\/td>\n<td><\/td>\n<td>*<\/td>\n<td><\/td>\n<td>18<\/td>\n<td>24<\/td>\n<td>19<\/td>\n<\/tr>\n<tr>\n<td>Dallas<\/td>\n<td><\/td>\n<td><\/td>\n<td>*<\/td>\n<td>18<\/td>\n<td>15<\/td>\n<td>25<\/td>\n<\/tr>\n<tr>\n<td><strong>Chicago<\/strong><\/td>\n<td>15<\/td>\n<td>18<\/td>\n<td>18<\/td>\n<td>*<\/td>\n<td>14<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>Atlanta<\/td>\n<td>14<\/td>\n<td>24<\/td>\n<td>15<\/td>\n<td>14<\/td>\n<td>*<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>Bakersfield<\/td>\n<td><\/td>\n<td>19<\/td>\n<td>25<\/td>\n<td><\/td>\n<td><\/td>\n<td>*<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div>\n<p>Step 2 (#4): Baltimore and Atlanta are the only non-visited cities connected to Chicago. For Baltimore, we calculate 15+37 = 52 and mark that distance. For Atlanta, we calculate 14+37 = 51. Since this is longer than the existing distance of 40 for Atlanta, we do not replace that distance.<\/p>\n<p>Step 3 &amp; 4 (#4): Mark Chicago as visited and Atlanta as current.<\/p>\n<table>\n<tbody>\n<tr>\n<td><\/td>\n<td>Baltimore<\/p>\n<p>[52]<\/td>\n<td>Denver<\/p>\n<p>[19]<\/td>\n<td>Dallas<\/p>\n<p>[25]<\/td>\n<td>Chicago<\/p>\n<p>[37]<\/td>\n<td><strong>Atlanta<\/strong><\/p>\n<p>[40]<\/td>\n<td>Bakersfield<\/p>\n<p>[0]<\/td>\n<\/tr>\n<tr>\n<td>Baltimore<\/td>\n<td>*<\/td>\n<td><\/td>\n<td><\/td>\n<td>15<\/td>\n<td>14<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>Denver<\/td>\n<td><\/td>\n<td>*<\/td>\n<td><\/td>\n<td>18<\/td>\n<td>24<\/td>\n<td>19<\/td>\n<\/tr>\n<tr>\n<td>Dallas<\/td>\n<td><\/td>\n<td><\/td>\n<td>*<\/td>\n<td>18<\/td>\n<td>15<\/td>\n<td>25<\/td>\n<\/tr>\n<tr>\n<td>Chicago<\/td>\n<td>15<\/td>\n<td>18<\/td>\n<td>18<\/td>\n<td>*<\/td>\n<td>14<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td><strong>Atlanta<\/strong><\/td>\n<td>14<\/td>\n<td>24<\/td>\n<td>15<\/td>\n<td>14<\/td>\n<td>*<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>Bakersfield<\/td>\n<td><\/td>\n<td>19<\/td>\n<td>25<\/td>\n<td><\/td>\n<td><\/td>\n<td>*<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div>\n<p>Step 2 (#5): The distance from Atlanta to Baltimore is 14. Adding that to the distance already calculated for Atlanta gives a total distance of 14+40 = 54 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 3 &amp; 4 (#5): 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 52 hours, and will route through Chicago and Denver.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<p>&nbsp;<\/p>\n<div class=\"textbox key-takeaways\">\n<h3>TRY IT NOW<\/h3>\n<div>\n<ul>\n<li>Find the shortest path between vertices A and G in the graph below.<\/li>\n<\/ul>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16203716\/Untitled16.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1848 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16203716\/Untitled16.png\" alt=\"Graph with 7 vertices labeled A, B, C, D, E, F, G. Edge between A, B is labeled 1, edge between A, C is 4, edge between B, E is 6, edge between E, G is 7, edge between G, F is 6, edge between f, c is 5, edge between c, a is 4, edge between c, d is 2, edge between b, d is 3 edge between e, d is 2, edge between e, f is 2, edge between f, d is 4.\" width=\"410\" height=\"236\" \/><\/a><\/p>\n<p><iframe loading=\"lazy\" id=\"mom5\" class=\"resizable\" src=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=6888&amp;theme=oea&amp;iframe_resize_id=mom5\" width=\"100%\" height=\"500\"><\/iframe><\/p>\n<\/div>\n<p>The following video summarizes the topics covered on this page.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-3\" title=\"Graph Theory:  Dijkstra&#39;s Algorithm\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/KvRwplnIoEM?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<\/div>\n\n\t\t\t <section class=\"citations-section\" role=\"contentinfo\">\n\t\t\t <h3>Candela Citations<\/h3>\n\t\t\t\t\t <div>\n\t\t\t\t\t\t <div id=\"citation-list-206\">\n\t\t\t\t\t\t\t <div class=\"licensing\"><div class=\"license-attribution-dropdown-subheading\">CC licensed content, Original<\/div><ul class=\"citation-list\"><li>Learning Outcomes. <strong>Provided by<\/strong>: Lumen Learning. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Revision and Adaptation. <strong>Provided by<\/strong>: Lumen Learning. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><\/ul><div class=\"license-attribution-dropdown-subheading\">CC licensed content, Shared previously<\/div><ul class=\"citation-list\"><li>Math in Society. <strong>Authored by<\/strong>: David Lippman. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"http:\/\/www.opentextbookstore.com\/mathinsociety\/\">http:\/\/www.opentextbookstore.com\/mathinsociety\/<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Pleasant View housing development. <strong>Authored by<\/strong>: Sam Beebe. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/flic.kr\/p\/5kTroZ\">https:\/\/flic.kr\/p\/5kTroZ<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Drawing a street network graph. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/youtu.be\/gyQhW24Dr2E\">https:\/\/youtu.be\/gyQhW24Dr2E<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/about\/pdm\">Public Domain: No Known Copyright<\/a><\/em><\/li><li>Drawing a graph for bridges. <strong>Authored by<\/strong>: OCLPhase2. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/youtu.be\/yn-OD8OBSDM\">https:\/\/youtu.be\/yn-OD8OBSDM<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Question ID 6885, 6883. <strong>Authored by<\/strong>: Lippman, David. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em>. <strong>License Terms<\/strong>: IMathAS Community License, CC-BY + GPL<\/li><li>Graph Theory: Dijkstra&#039;s Algorithm. <strong>Authored by<\/strong>: James Sousa (Mathispower4u.com) . <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/youtu.be\/KvRwplnIoEM\">https:\/\/youtu.be\/KvRwplnIoEM<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Question ID 6888. <strong>Authored by<\/strong>: Lippman, David. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><\/ul><\/div>\n\t\t\t\t\t\t <\/div>\n\t\t\t\t\t <\/div>\n\t\t\t <\/section><hr class=\"before-footnotes clear\" \/><div class=\"footnotes\"><ol><li id=\"footnote-206-1\">Bogdan Giu\u015fc\u0103. http:\/\/en.wikipedia.org\/wiki\/File:Konigsberg_bridges.png <a href=\"#return-footnote-206-1\" class=\"return-footnote\" aria-label=\"Return to footnote 1\">&crarr;<\/a><\/li><\/ol><\/div>","protected":false},"author":21,"menu_order":2,"template":"","meta":{"_candela_citation":"[{\"type\":\"original\",\"description\":\"Learning Outcomes\",\"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\":\"cc\",\"description\":\"Pleasant View housing development\",\"author\":\"Sam Beebe\",\"organization\":\"\",\"url\":\"https:\/\/flic.kr\/p\/5kTroZ\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Drawing a street network graph\",\"author\":\"\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/gyQhW24Dr2E\",\"project\":\"\",\"license\":\"pd\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Drawing a graph for bridges\",\"author\":\"OCLPhase2\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/yn-OD8OBSDM\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Question ID 6885, 6883\",\"author\":\"Lippman, David\",\"organization\":\"\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"IMathAS Community License, CC-BY + GPL\"},{\"type\":\"original\",\"description\":\"Revision and Adaptation\",\"author\":\"\",\"organization\":\"Lumen Learning\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Graph Theory: Dijkstra\\'s Algorithm\",\"author\":\"James Sousa (Mathispower4u.com) \",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/KvRwplnIoEM\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Question ID 6888\",\"author\":\"Lippman, David\",\"organization\":\"\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"}]","CANDELA_OUTCOMES_GUID":"","pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-206","chapter","type-chapter","status-publish","hentry"],"part":178,"_links":{"self":[{"href":"https:\/\/courses.lumenlearning.com\/suny-hccc-ma-124-1\/wp-json\/pressbooks\/v2\/chapters\/206","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/courses.lumenlearning.com\/suny-hccc-ma-124-1\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/courses.lumenlearning.com\/suny-hccc-ma-124-1\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/suny-hccc-ma-124-1\/wp-json\/wp\/v2\/users\/21"}],"version-history":[{"count":2,"href":"https:\/\/courses.lumenlearning.com\/suny-hccc-ma-124-1\/wp-json\/pressbooks\/v2\/chapters\/206\/revisions"}],"predecessor-version":[{"id":1136,"href":"https:\/\/courses.lumenlearning.com\/suny-hccc-ma-124-1\/wp-json\/pressbooks\/v2\/chapters\/206\/revisions\/1136"}],"part":[{"href":"https:\/\/courses.lumenlearning.com\/suny-hccc-ma-124-1\/wp-json\/pressbooks\/v2\/parts\/178"}],"metadata":[{"href":"https:\/\/courses.lumenlearning.com\/suny-hccc-ma-124-1\/wp-json\/pressbooks\/v2\/chapters\/206\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/courses.lumenlearning.com\/suny-hccc-ma-124-1\/wp-json\/wp\/v2\/media?parent=206"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/suny-hccc-ma-124-1\/wp-json\/pressbooks\/v2\/chapter-type?post=206"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/suny-hccc-ma-124-1\/wp-json\/wp\/v2\/contributor?post=206"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/suny-hccc-ma-124-1\/wp-json\/wp\/v2\/license?post=206"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}