Oh, now we're going to describe one of the most important algorithms in computer science, the Dijkstra Shortest Path Algorithm. Edsger Dijkstra is a Dutch computer scientist, and he's one of the most important figures in modern computer science. He was involved in computer language design, ideas in compiling, ideas in the semantics, correctness of programming. And he invented a number of very, very clever and important algorithms. Dijkstra started his career in the Netherlands at the Mathematical Centrum. And later became a professor at the University of Texas in the United States. And he's also one of the very first people to win the Turing Award, which hopefully most of you know about. But if you don't the people who've won the Turing Award are what the analogy is MacArthur Prizes or Nobel Prizes. We don't have such things in computer science, per se, and the Turing Award is considered our Nobel Prize. So in the Dijkstra Shortest Path Algorithm that we're going to describe, we're going to use undirected graphs with weightings(with cost). So costs are going to all be non-negative. And conceptually, what you should keep in mind is a road map, and the canonical problem is finding the shortest route from one place to another. So, if you're looking for a road trip and you're going between Chicago and Los Angeles, and you want a shortest path, you have a very big map. Lots of roads. You typically might go to AAA and get some specific assistance. Or nowadays, you can just use your on-board trip computer. And they indeed in, in some important sense (it has embeded )the Dijkstra algorithm. We're going to learn how to program this critical algorithm and indeed, it's going to be our next programming assignment. So, the idea is we have a source and a destination. Chicago to Los Angeles. And between the source and destination, we want to find a shortest path. The critical steps in the Dijkstra algorithm are to maintain what I call two sets. One is a set of closed nodes. The closed nodes are nodes that have, have known shortest distances. Now if we're starting from Chicago, what do we know? Right off the cuff, we know the shortest distance from Chicago to Chicago. That's zero. That's like trivial case. So, the algorithm would start with the source node being put in the closed set, and that source node would have value 0. And then, in the open set, we would look for immediate successors of s. And place their distance in the open set. So the open set is what's reachable. And at any time in the open set, we have what's reachable. And we have a calculation based on the edge cost from things in the closed set. And what we do, our major iterative step is we pick the open note in that list, who's cost is least. Pick the open node who has least cause. Whoops, least cost, not list cost, least cost. Confusing list and least. Okay. If in this iterative step, we pick a node that is the termination node. If we've, are moving along from Chicago, and we've reached Los Angeles. And Los Angeles gets thrown in the closed set, we can stop. The algorithm guarantees that when the destination node is placed in the closed set, calculation is provably a shortest distance. If the destination node is not the node picked as the next least node from the open set, we compute all the direct successors from that node. So if that node, so we, n has least cost. We look at the edges out of n. And they have a cost. It might be cost of n to j, where (n,j) are the determiners of the edge. And n will have a value, which is its value of the, the cost from s, from the source. So n has some cost, some current cost, back to s. And that cost, whatever that is, s to n plus cost ( n , j) is what it takes to reach j. Now either j is already in the open set. we have like, three cases. J is in the closed set. If j was already in the closed set, we don't need to bother with it, because we already know by the nature of Dijkstra's algorithms that we have a shortest path to j. If j is not in the open set, or the closed set, then we put it in the open set. We now have a new path, a way to get to j. So we're somewhere, past Chicago. Maybe we're approaching Kansas City and we haven't yet reached Kansas City in any kind of path that we've calculated. And we see we can get to Kansas City. That would be placed in the open set with whatever it's value is, traced back to Chicago. And the last case is, we already had an alternative route. We had a pre-computed route. So j, or Kansas City, in this case, was already in the open set. But this new route improves on the old route because we're trying to search for least costly paths. In that case we update the paths. So we have three conditions, open set, a possibility for updating, or it's already in the closed set. And then if the node d is picked, we stop. There's no further need to look for successors. Or if there's no more successors, we can't get to d. So if we try to go from Chicago to Honolulu, we would find all sorts of paths to places like Seattle and El Paso, and God knows what else, Los Angeles, but we would have no road route to Honolulu. So we would exhaust, if we had tried to put into our travel computer, find me a road from Chicago to Honolulu, it would stop. And otherwise some shortest path tree is maintained in the calculation. And that lets us, when it's done, having stopped at d, not only have the value of the shortest route but be able to trace back the shortest route. So I'm going to simulate Dijkstra by hand. And I'm going to simulate it on this next map. And I'm going to draw things in red and I'm going to start with S. And I'm going to want to get us to T. In this case, I'm doing it in a directed graph. So this was just the case that I had manufactured and I'll show it to you in the directed case, but it, it shouldn't be any different in the undirected case. So initially, the open set s has value 0, and then s can reach a. So this is the closed set, and its value is 4. S can reach b, and its value is 3. S can reach d, and its value is 7. And that's it. The out degree edges of s are 3. So now we look at the open set. We pick s equals b, so b comes into the closed set with value 3. So in some sense, Dijkstra's algorithm has picked out this. And now b becomes the node we expand from, and so we search b. Now b can go back to s, but that's not a value, since s is in a closed set. And b can go to d. So we have to check if b went to d, it would be 3 plus 4. But we already of d at 7, so there's no reason to update it. And that's the only two ways we can go. So there isn't anything new in the open set. So we would come back, and we would get as our least value, a, whose value is 4. And so now, our Dijkstra's shortest path tree would be at this point in the second iteration also s going to a with 4. Now a has some new things we can go to. So from a we can go to c. The value was 4 plus 1, so now it's 5. And that's the only thing a can go to. But 5 is indeed the best value, so we put in c in the closed set. The c's value equal 5. And c can reach e with value 6. And c can reach d, and that would be value 8. 8 doesn't improve on 7, so we don't update that. But we can go c to e, and that's value 6. So now we cross out this. We get e. We get it equal 6. We go back and we find we can go to e. Oops, no e already went to (6 -sic). Excuse me, we go back and e is now in the open set. e has to be expanded. So we get, we can look at e to d. Now e can't go to d directly, that's the wrong direction. But e can go to g and g is value 8. And e can go to t, so it can go to g for value 8. It can go to t, and that's value 10. Now just because we can reach t, which is our destination, the terminus, doesn't mean we go there. because this is still in the open set. The only time we're guaranteed a best or least costly path is when something's been stored in the, in the closed set. And there's still values less than 10. So they have to be explored. The next value that needs to be explored is s going to d at 7. So s going to d at 7 makes d equal 7 in the closed set. And then we have d can go to f. So 7 plus 5 is 12. d from here can go to t. So that's 7 plus 3, which is 10. But that hasn't improved the value, so we don't update anything. And d can go to e, but e is in the closed set, so we don't do anything with that either. So here we go back, we look. We've got an e going to g (value) 8. And from g, we can go back to e. e is already in the closed set. We can from g to t. But 8 plus 3 is 11. We don't improve on 10. So we leave it alone. We're done with the updates. We come back, select the node. And now we find e to t, which is value 10. And e to t, so t equals 10. We can terminate. And if we keep our back lengths in this map, we can even find the shortest path. Now notice it wasn't unique. We could have found the shortest paths, which would have been s to d and d to t. That would have also been 10. So this doesn't guarantee any kind of uniqueness, but it does guarantee that we get a least costly path. You should practice with other graphs. And the assignment I'm giving out now is that you will try to do a Dijkstra Shortest Path Algorithm, which will mean that you need to decide on a representation. my recommendation is the list representation's a little more flexible. But it's perfectly okay if you do the matrix representation, or even do both, depending on how ambitious you are. And that'll be an assignment that I'll be expecting for the next turn in time.
