in this video we look at how to understand and be able to trace dykstra's shortest path algorithm and be aware of the applications of the shortest path algorithm DX's shortest path algorithm finds the shortest path between one node and all other nodes on a weighted graph it is considered a special case if the AAR algorithm with no htics although Ed dyra actually developed his algorithm first it's also a type of breadth first search now a limitation of dyra shortest path is that it doesn't work for edges with a negative weight value the bman Ford algorithm later provided a solution to this problem but it's not covered as part of your course edar dyra developed this algorithm to find the shortest route of travel between Rotterdam and gran it can be used for many purposes but the shortest path between two points needs to be established for example GPS navigation IP routing telephone networking as we've already mentioned dyra shortest path algorithm will find the shortest path between a specified start node and all the other nodes in a weighted graph and this is similar to a bread first search which we learned about in the video titled SLR 5 five graph traversal algorithms we're going to use a table prepopulated with nodes that's a through G to help us work through this algorithm we've got one row for each the use of a table or array is just one approach to implementing dyra shortest path algorithm you could just as easily do this with a Q structure and a series of lists we're going to use this table to help us work out the shortest path from a to all other number noes before we start you will notice we've prepopulated the table with some additional data we've indicated that no nodes have been visited as of yet we also need to set an initial starting distant for each of the nodes this initial number should be very large and the reason for that will become clear as we work through the algorithm here we've used Infinity as the default starting number note the shortest distance from the starting node a to itself is obviously zero here are the steps presented in simple Structured English that we will now follow to calculate the shortest path from the starting node a to all other nodes it is separated into two parts the first part shown in yellow calculates the shortest path from a specified node to all other nodes the second part shown in red outputs the shortest path from the start node to a specified goal node so find the node with the shortest distance from the start which has not been visited well that is node a which is a distance from the start node of zero whereas all the others are currently Infinity we now need to consider each connected node that's not yet been visited well that's b c and d let's look at B first we need to calculate its distance from the start which is equal to A's distance from the start plus the edge weight so that's not + 4 equals 4 we now check if B's distance from the start is lower than its current recorded distance from the start well four is clearly less than infinity so we have to carry out two actions we update B's distance from the start to the newly calculated distance of four and we set the previous node column to be the current node which is a next we do the same thing for nodes C and D remember each node's distance from the start is equal to A's distance from the start plus the edge weight so 0 + 3 is 3 that's for C and 0 + 2 is two for D well again three and two are clearly both less than infinity so we update C and D's distance from the start and set the previous node to a we're now finished with node a so we mark it as visited so once again we need to find the node with the shortest distance from the start that's not yet been visited well that's D it has a distance from the start of two we then consider each node connected to d That's not yet been visited and that's C and F this time each nose distance from the start will be equal to D's distance from the start plus the edge weight so for C that's 2 + 1 equals 3 the newly calculated distance from the start is not less than the recorded distance from the start so no update is required this time remember the distance from the start is equal to D's distance from the start plus the edge weight so for f that's 2 plus 2 is four well four is less than infinity so we do update node s distance from the start we now finish with node D and we mark it is visited so once again we find the node with the shortest distance from the start that's not yet been visited so that's now C which has a distance from the start of three we consider each node connected to C that's not been visited well there are none so we simply mark this node as [Music] visited now the node with the shortest distance from the start not yet being visited is either b or F they both have a distance from the start or four so we'll choose B we could have chosen F instead it doesn't matter which one you choose it all comes down to how the algorithm is implemented we consider each node connected to B that has not been visited well that's just e here the distance from the start will be equal to B's distance from the start plus the edgeway so that's 4 + 4 = 8 8 is less than infinity so we update node E's distance from the start we're now finished with node B so we mark it is visited once again we find the node with the shortest distance from the start that's not yet been visited and that's f with a distance of four we consider each node connected to F that's not being visited and that's just G here the distance from the start will be equal to F's distant plus the edge waiting so that's 4 + 5 is 9 9 is less than infinity so we update node G's distance from the start we're now finished with node F so we mark it is visited we find the node with the shortest distance from the start that's not been visited well that's now e with a distance of eight we consider each node connected to e that's not been visited and that's G here the distance from the start will be equal to e distance from the start plus the edge weight so 8 + 2 is 10 well the newly calculated distance from the start is not less than the current recorded distance from the start which is nine so no update is required at this stage we're now finished with node e the market is visited we find the node with the shortest distance from the start that's not been visited well it's only G that's left and we consider each node connected to G that's not being visited well there are none so we simply mark this node is visited as there are no unvisited nodes left the algorithm is complete to find the shortest path from one node to any other node we start with our goal node and simply follow the previous nodes back to the start inserting the new node at the front of the list so for example the shortest PA from a to G would be a to d to F to G let's consider a practical application of this algorithm here's an abstraction of a map of the county of gler with some of its towns shown say we were traveling between ches spry and stoud in the shortest possible time which route would we take well dyra shortest path algorithm will answer that question for us we would need to store the relevant information in a graph data structure each town would become a node The Roots between the nodes would become the edges the distance between each node would become the edge weightings using abstraction we can ignore the actual geography and layout of the roads indeed we can do away with the map completely all we need to consider for the algorithm is the nodes the edges and their weightings just before we work through this second example let's look at some pseudo code for one possible implementation of dyra shortest algorithm if you study the pseudo code you can see a clear match to the Structured English this could be implemented in any language you choose and although you're not required to write the code for this algorithm you are expected to be able to understand and trace it okay so let's work through this code again we start by initializing the distance from the start value of all nodes to Infinity except for the starting node which we set to zero that's T we start with no t as it has the shortest distance from the start out of all unvisited nodes pause the video and see if you can work out the state of this table after the steps highlight and yellow have been carried out okay so how did you do the nodes connected to T that have not yet been visited are G and C here the distance from the start will be equal to T's distance from the start plus the edge weight so G is not + 133 and F is not + 9 13 and 9 are both less than infinity so we update nodes G and F's distance from the start as well as setting their previous node to T so which node would we go to next well node C would be next as it has the shortest distance from the start of all the remaining unvisited nodes of nine pause the video again and work out the state of this table after the steps highlight in yellow have been carried out okay how did we do the nodes connected to C that have not yet been visited are g s and I this time now here the distance from the start will be equal to C's distance from the start plus the edge weightings so we have 9 + 8 is 17 for G 9 + 14 is 23 for s and 9 + 15 is 24 for I now in this case node G 17 is not less than the current recorded value of 13 so no updates required but the 23 and 24 are both less than infinity so we update nodes s and I's distance from the start and set their previous node to C so which node would we go to next well node G would be next as it has the shortest distance from the start of all the remaining unvisited nodes that's 13 pause the video once more and work out the state of this table after the yellow highlighted steps have been carried out the nodes connected to G that have not yet been visited are B and S here the distance from the start will be equal to G's distance from the start plus the edge weight so we have 30 for B and 23 for s 30 is less than infinity so we do update node B's distance from the start but in the case of node s 23 is the distance from the start value that we already have recorded so no update is required so which node would you go to next well it would be node s next as it has the shortest distance from the start of all the remaining unvisited nodes of 23 pause the video once more and see if you can work out the state of this table okay so the nodes connected to s that have not yet been visited a b and I when we work out the waiting we have B at 37 and I at 38 in the case of node B 37 is greater than the value already recorded of 30 so no update required and in the same way 38 is greater than 24 so we don't update node I's distance from the start either we already have shorter Roots which node would you go to next well it will be I it has the shortest distance from the start of all the remaining unvisited nodes at 24 pause the video and work out what this table should look like well I has no nodes connected to it that haven't already been visited so we simply mark it is visited and move on we can see that b will be the final unvisited node as before with i b has no nodes connected to it that haven't already been visited so we mark it as visited a move on there are no more unvisited nodes so we know the algorithm must be complete so using this data can you answer the original question what is the shortest path between ches spry and stra pause the video and work out your answer and to find the shortest path we start with the gold node that's stoud and we follow the previous nodes back to the start chre inserting the new node at the front of the list so the shortest path from chury to stoud is chury cheltonham to stoud so let's consider a few final thoughts on this shortest path algorithm you might have spotted that the shortest path we identified during the walk through was T Cs and had a distance of 23 but there is an alternative but equally valid shortest path that has a distance of 23 and that's t g to S if there happens to be more than one shortest path the algorithm will just show you one possible route when you output now you already understand that we need to set the initial distance from the start values to a very large number in our example we chose Infinity but how do you actually set Infinity in a programming language as ironic as it may seem Infinity is defined as an undefined number that can have either a positive or negative value the concept of representing Infinity as an integer kind of violates its definition so as of 20 20 there is no way to represent infinity as an integer in any programming language what you really need is simply a very large number that you can be sure will always be bigger than any possible Edge value as python is a dynamic language float values can be used to represent an infinite integer and you can literally use float INF to represent infinity the highlighted line of code creates a positive Infinity float as a side note Infinity can be both positive and negative and python supports both imp and negative imp Visual Basic uses a different approach and simply assigns the largest possible number that can be stored in a 32-bit 4 by integer as a constant called Infinity having watched this video you should be a to ask the following key question do you understand how dyra shortest path algorithm works and can you trace its code to explain how it works Dave and I know that data structures and algorithms are one of the hardest areas of the course and we've therefore written a dedicated book which is available to purchase on Amazon the book covers all the data structures and algorithms you need to be aware of for the exam each one has its own dedicated chapter the chapter overviews the data structure or algorithm gives you applications operations links to our videos online and goes over the algorithm in simple Structured English a visualization pseudo code and is fully coded in Python C and Visual Basic [Music]