Discrete Math II - 10.6.1 Shortest Path Problems - Dijkstra's Algorithm

Summary

In this video, Kimberly Brehm teaches viewers how to solve shortest path problems using Dijkstra's Algorithm, applied to a weighted graph. The main aim is to determine the shortest path from a specified starting vertex to others, without forming a minimum spanning tree. The algorithm involves labeling distances, systematically visiting vertices, updating the path, and progressively determining the least costly journey to unvisited nodes. After a detailed explanation, Brehm walks through an example demonstrating how to implement the algorithm using both graphical and tabular methods while highlighting the importance of documenting steps for clarity, especially for students. Finally, viewers are encouraged to attempt an example independently, using Brehm's step-by-step instruction as a guide.

Highlights

• Learn how Dijkstra's Algorithm solves shortest path problems! 🚀
• A weighted graph is your model; it can be directed or undirected depending on your needs. 🕸️
• Not a minimum spanning tree – focuses on the cheapest or shortest path to each node instead. 🌳
• Label your starting vertex as 0 and all others as infinity to start. 🔍
• Use graphs, tables, and methodical updates to track progress through the algorithm. 📈
• Practice makes perfect: try examples yourself to solidify your understanding. 💪

Key Takeaways

• Dijkstra's Algorithm finds the shortest path in weighted graphs, not a minimum spanning tree! 🎯
• Start by labeling the starting vertex distance as 0 and others as infinity; update as you go. 🔢
• Always choose the unvisited vertex with the smallest known distance next. 🏃‍♂️
• Keep track of each step, whether through a table or graph; your instructor might prefer one method. 📋
• Try practicing step by step to ensure you understand the sequence; reverse engineer to find the path. 🔄

Overview

In the realm of discrete mathematics, tackling shortest path problems is a vital skill, especially when wielding the power of Dijkstra's Algorithm. Essentially, this algorithm helps you decode the quickest routes within a weighted graph, being either directed or undirected, by focusing on individual vertex connections rather than spanning across all nodes.

Throughout her engaging video lesson, Kimberly Brehm provides a meticulous walkthrough, showcasing the step-by-step application of Dijkstra's Algorithm. She explains the intricacies of labeling and recalculating distances from a chosen starting vertex while emphasizing that every step must be documented, whether utilizing graph redraws or table entries. This clarity is crucial for students who must display their reasoning explicitly.

Brehm even lends a tips-of-the-trade approach, suggesting students approach each example methodically and attempt problems independently for reinforced learning. Utilize tables or drawn graphs as means to visualize calculations and paths, all the while ensuring clarity in your steps, which will make instructors pleased and confident in your problem-solving prowess.

Chapters

• 00:00 - 00:30: Introduction to Shortest Path Problems and Dijkstra's Algorithm The chapter introduces the concept of shortest path problems in graph theory and presents Dijkstra's algorithm as a method for finding solutions to these problems. It describes the use of weighted graphs to model these problems, where the graph can be directed or undirected. Each edge in the graph is labeled with metrics such as travel time, cost, or distance, indicating the terms under which the 'shortest path' is calculated.
• 00:30 - 01:00: Modeling with Weighted Graphs The chapter focuses on modeling with weighted graphs, particularly in finding optimal paths in terms of time, cost, or distance between vertices. An example is provided where vertex a is the starting point, and the goal is to determine the fastest routes from vertex a to other vertices such as b, c, and d.
• 01:00 - 01:30: Understanding the Difference: Shortest Path vs. Minimum Spanning Tree The chapter discusses the distinction between shortest path algorithms and minimum spanning tree algorithms. It emphasizes that the concept being explained is not related to minimum spanning trees, clarifying that if students haven't yet encountered minimum spanning trees in their studies, they will do so later. The discussion includes an initial focus on the essential difference, noting that in a minimum spanning tree, there is typically a starting vertex involved in creating the tree structure.
• 01:30 - 04:00: Dijkstra's Algorithm Explained Step by Step Dijkstra's Algorithm focuses on finding the cheapest path to visit each individual vertex in a graph, differentiating it from a minimum spanning tree that finds the cheapest way to visit all vertices. This chapter aims to convey the algorithm in plain language, ensuring an understanding of how it operates step-by-step.
• 04:00 - 05:30: Example Walkthrough Using Dijkstra's Algorithm The chapter provides a walkthrough of using Dijkstra's algorithm. It begins by establishing a starting vertex, in this case, 'A', and assigning it a distance of 0. All other vertices are initially labeled with a distance of infinity to represent a very large number. As the process continues, these distances will be recalibrated based on a set of iterative steps defined prior. The algorithm entails looking at any unvisited neighboring vertices from the current vertex being evaluated.
• 10:30 - 11:00: Practice Problem Introduction The chapter introduces a practice problem related to graph traversal algorithms. The main focus is on understanding how to find the shortest path from a starting point, 'a,' to adjacent vertices. Initially, all known distances are set to infinity except for the starting point. The chapter explains the process of evaluating each connected vertex, updating the path distance if a shorter path is found, and retaining the existing path if not. The overall goal is to optimally traverse the graph by continually visiting or selecting the next vertex to examine based on the shortest known distance.
• 11:00 - 18:00: Solving the Practice Problem The chapter "Solving the Practice Problem" discusses an algorithmic approach to traversing a graph. Specifically, it focuses on choosing the unvisited vertex with the smallest known distance from the start vertex to optimize the path. It mentions that different resources, like textbooks or online videos, might depict this process through various strategies, such as using tables or redrawing the graph for each step. The chapter assures that although methods may vary, the underlying algorithm remains consistent.

Discrete Math II - 10.6.1 Shortest Path Problems - Dijkstra's Algorithm Transcription

• 00:00 - 00:30 in this video we're going to take a look at shortest path problems and a way to solve them and that way is dijkstra's algorithm so the way that we're going to model this is using something called a weighted graph and in a weighted graph it can be directed or undirected obviously the graph model i have here is undirected and essentially we're just going to label each edge with a travel time a travel cost a travel distance or
• 00:30 - 01:00 whatever it is that we're trying to model with that particular graph and then we can use those to determine the shortest time or the least cost or the shortest distance between some starting vertex and any other vertex so in our example we are going to use vertex a as the starting vertex and what it's going to do is it's going to find the fastest way to get to b the fastest way to get to c the fastest way to get to d and the fastest way to get
• 01:00 - 01:30 to e or cheapest whatever it is that you're modeling however it's important to note that this is not a minimum spanning tree algorithm so if you are in my class you don't know what a minimum spanning tree is yet we're going to learn that in a little bit so perhaps that's not confusing to you if you've studied studied minimum spanning trees that is a tree that's going to have some beginning vertex like a
• 01:30 - 02:00 and then the cheapest path or cheapest way in order to visit each other vertex so it is a little bit different in that this is not a minimum spanning tree it's not the cheapest way to visit all of the vertices it's the cheapest way to visit each individual vertex so i wanted to give you the actual algorithm in plain language just so you understood exactly what it is that we're going to do
• 02:00 - 02:30 and then we're actually going to work through this together so to begin we're going to choose our starting vertex i've already told you we're going to start with a so we're going to label that distance 0 and all of the other distances we're going to label infinity because we want it to be a very large number and eventually we will replace each distance with another distance based on the repeating steps that i've given you for the repeating steps we're going to examine any unvisited neighbors from our visiting vertex so
• 02:30 - 03:00 again we're going to begin at a so we're going to look at anything that is connected to a so any adjacent vertices to a and we're going to look at the distance from that vertex and if the distance is less than the known distance so at first it's definitely going to be because our known distance is going to be infinity to any other distance then we're going to relabel the distance in the path and if it's not we'll leave it as is and then we're going to visit or choose
• 03:00 - 03:30 the unvisited vertex with the smallest known distance from the start vertex and then we're just going to keep doing that until we have visited every single vertex now different textbooks different videos you may find on youtube have you perform this algorithm in different ways so it's still the same algorithm but it might be that you use a table or it might be that you redraw your graph for each step so in your textbook
• 03:30 - 04:00 it takes you through how to do the redrawing for each step i'm going to do sort of an abridged version of that because i'm too lazy to redraw my graph each time and i'm also going to show you how to use a table because i feel it's probably the easiest way to do it we're going to do this example step by step and as we are working through this i'm going to show you both how i would like you as my student to show work on a table or show work on
• 04:00 - 04:30 the graph now if you are watching this video on youtube and i'm not your instructor i would make sure that you reach out to your instructor to see how he or she would like you to show your work for my students i do want to see the process involved so i don't just want to see the final outcome but i want to see the steps that you took so that's what i'm going to model here as we go through this example so as you can see i have my weighted graph and we've already determined that we are going to begin at a so dijkstra's algorithm says determine your
• 04:30 - 05:00 starting node okay that's a and label that distance as 0 and label all other distances as infinity so if i'm using the show work on the graph method that's how i show work on the graph so far if i'm using the table i would say the shortest distance of a is 0 and the path for a i don't have to worry about because to get from a to a i didn't go anywhere but everything else
• 05:00 - 05:30 i'm going to use a distance of infinity and if you'll notice i'm drawing infinity not super big because i'm saving room in that table to show the next steps so the next step from a is first to indicate that a has been visited so i'm just going to circle it to know that it has been visited and then i need to look at any unvisited vertices so to get from a to b that would take a distance or cost of 5.
• 05:30 - 06:00 now 5 is kind of a lot but it is less than infinity so i'm going to cross off infinity and replace it with a cost of 5 and the path comes from a and again i would do the same thing over here i would replace it with 5 and a path of a so depending on how you're showing work then i'm going to look at e well to get to e i have 3 coming from a
• 06:00 - 06:30 and again 3 coming from a and to get to d is a distance of 1 coming from a so d is 1 and a the next step is to choose which vertex i would not like to next visit and the next visiting vertex should be the cheapest one or the shortest one whatever the the least amount is so we can tell very easily that that is one for d
• 06:30 - 07:00 so i'm going to visit d and that means that again the shortest distance is one and that path is a comma d and again i can either write a comma d here i typically just leave it as a if i'm showing it there now i have to look at each distance i shouldn't have used blue that might get confusing but we're going to go with it i have to look from d to each unvisited
• 07:00 - 07:30 vertex so as you can see e has already been relabeled as 3a but it's not a visited vertex it's still an unvisited vertex because i've only visited a and d so far whoops i should circle d right here so now i'm going to look at e and to get to e from d would have a distance of one plus three so that's a distance of 4.
• 07:30 - 08:00 now 4 happens to be greater than the 3 that's already there so i'm not going to relabel e because we're only going to relabel if the cost is less then the other unvisited vertex is c and that would have a distance of one plus one or two so this is two comma a d so from here i'm going to look i'm sorry i should have replaced it over here as well to
• 08:00 - 08:30 a d from here i'm going to look at any of the unvisited vertices and determine which is cheapest to get to and that answer is c to get to c i'm going to take a to d so now my cost is 2 and my path is a d and i'm just going to write adc a d c now whether or not you include the c
• 08:30 - 09:00 is sort of up to you i find it easier to include the c but again as you can see over here i only have a d so now i have visited c and i only have two more unvisited vertices of b and e coming from c i now have to look at those two unvisited vertices and see if i can change any of the values so to get to e from c
• 09:00 - 09:30 i would have a distance of two plus one which is three now 3 is the same as 3 so i'm just going to leave it as is to get from c to b would have a distance of 2 plus 1 which is 3. well 3 is less than 5. so i'm going to replace 5 with 3 and instead of going straight from a we went from a to d to c
• 09:30 - 10:00 so now b is replaced with 3 and a is replaced with adc so now what well now i have to choose a vertex to visit now you can see both b and e have a cost of three or distance of three and so it really doesn't matter which one i choose because it's going to be
• 10:00 - 10:30 the same so i'm going to go ahead and choose b to visit so b has been visited the cost is 3 the path is a d c b or you can leave it just as is up here 3 adc and then of course the last one is e so we're going to visit e and that has a cost of 3 and then that's a e or just 3a so as you can see it's kind of the same
• 10:30 - 11:00 process whether i'm using a table or a graph and this tells me from a the shortest path to b is a distance of 3 and we go from a to d to c to b to get to c the shortest path is 2 or distance is 2 and the path is adc to get to d the shortest path is 1 and that's just straight from a to d and to get to e the shortest path is three
• 11:00 - 11:30 and that's from a to e here's a question for you to practice on your own so try this question when you're ready press play to see how you did again we're going to begin at a i should have made that clear from the beginning but the distance to get to a is zero and all of the other distances are infinity so so far so good now i'm going to
• 11:30 - 12:00 choose a and say okay i did choose a i'm going to start there i have visited a where can i get to from that visited vertex so the visited vertex is a and i can get to either b which is a distance of 2 so i'm going to replace infinity with 2 coming from a and if you want you can write a b you might also see videos out there that just have you write the previous vertex
• 12:00 - 12:30 which is a little bit cleaner but you have to do a little bit more work to find the path so if i just i'll just put these over here just so you can see one more way in which you can show this work but b has a weight of 2 coming from a and c has a weight of 3 coming from a or again the path would be a c or the path would be a b now from here what am i going to do i'm going to find the cheapest path so this
• 12:30 - 13:00 fastest or cheapest way is to get to b because 2 is less than 3. so i'm going to choose b i should have circled that a already so i visited a i'm now visiting b and again b has a distance of two and a path of a b or a previous vertex of a so from b i'm now going to look at any adjacent vertices so from b i can get to d which would be
• 13:00 - 13:30 2 plus 5 or 7. so d is going to be replaced with 7 and that path is a b d or a previous vertex of b depending on how you'd like to show your work i could also get to e e would be a path of two plus two which is four and that path would be a to b
• 13:30 - 14:00 to e or a previous vertex of b i can't get anywhere else so z is still not attainable from where i'm standing so now i'm going to choose what is the cheapest vertex next so that in this case is c because 3 is the lowest number so i keep forgetting the circle thing so i'm going to choose c and c is going to be the next vertex
• 14:00 - 14:30 that i visit so we now have 3 and then ac locked in and now i'm going to look at any vertices adjacent to c so c can get to e now that path would be 3 plus 5 which is eight and currently e has a path or a weight of four so i'm not going to relabel e because it would just be more expensive or more time or more distance so now i'm just looking at four and
• 14:30 - 15:00 seven and saying which one's smaller four or seven so obviously four is smaller so i'm going to choose e so e has now been visited with a distance of 4 and a path of abe and i'm going to relabel any vertices that i can't so to get to d i would have the 4 that it takes to get to e plus 1 more which is a distance of five total currently the distance is seven so five is better than seven so
• 15:00 - 15:30 i'm re-labeling d with five and that new path is a b e d or the new previous vertex is that it's coming from e now i'm looking oh and then i have to look at z and say can i relabel z well yes i can so from to get to e was four plus it's four more to get to z so now z is getting replaced with four plus four or
• 15:30 - 16:00 eight and that is a b e z or previous vertex of e now i'm going to look at the five and the eight and choose the smallest of five and eight which is of course five i'm trying to find a color we haven't used and i'm striking out oh purple so i'm going to choose five so now i'm choosing d to visit d has a weight of five the path was a b
• 16:00 - 16:30 e d or a previous vertex of e and the only thing i have left to do is either choose z to be 8 or see if i can get to z faster going through d so to get to d was a weight of 5 and to get from d to z is two so five plus two is seven and seven is better than eight so i'm going to replace eight with seven and this path now becomes because i'm
• 16:30 - 17:00 coming from d a b e d z or a previous vertex of d so now i've done it i've found the cheapest path and of course then i would choose z so i found the cheapest path to each of these vertices so so if i need to get from a to d the cheapest is five with a b e d is the path or again if
• 17:00 - 17:30 you're just looking at the previous vertex so if you're just showing this you can find the path you would just have to do some backtracking so let's say i was focused on z z says okay you had to get to d first and d said okay we had to get to e first and e said you had to get to b first and b said you had to get to a first so it's sort of gives you that path backwards so up to you if you want to do just the
• 17:30 - 18:00 previous vertex or if you want to write out the entire path or if you want to show the work on the table or on the graph you do you but just make sure that your steps are clear if you are in my class because i will want to see what steps you followed to find the solution now if the question said fine just use dijkstra's algorithm showing the table would be sufficient all of the work that i've shown in the table if it specifically said find the
• 18:00 - 18:30 shortest path to z then you would say a b e d z and then with a distance of four i'm sorry of seven so you would want to make clear that that was the final solution up next we're going to take a look at graph coloring