How to Find the Shortest Path – Intro to Algorithms

How to Find the Shortest Path – Intro to Algorithms


Let’s take a look at an approach for actually finding shortest paths in graphs, and we’ll use this example once again. It will help to actually have names for the other nodes, so I’m going to add these in. Just remember what breadth-first search does for this graph starting from A. We mark A as visited and we add it to the open list. We pull off the open list and add all the neighbors of A to the open list. Letter C, B, and D then we choose one of these nodes, Let’s say C and add all its unexpanded neighbors to the graph, but all its neighbors are expanded. Do the same thing with B. B has F, and D’s unexpanded neighbors are E. Now, F’s unexpanded neighbors are G, and E has no more unexpanded neighbors. We finish this step for a search. What we get here is that by the assumptions of breadth-first search, the shortest path from A to B is this direct link from A to B. The search would have actually terminated here, but we ran that anyway. These are supposedly the shortest paths in terms of number of hops to all these nodes. It actually makes sense. One hop to C. One hop to B. One hop to D. Two hops to F, sure. Two hops to E, sure. Three hops to G, one, two, three. Yep. There’s no faster way to get to G. This actually does the right thing in terms of number of hops, but let’s take a look at what happen when we went to expand B. At this point, even though we have a shortest hop path to B, we don’t have a shortest link path to B. All we know is that from A, you can reach C in three steps. Well, that’s really all we know. Even this A to D, we don’t know, there might be like a half weight path that goes from C to D, but we do know that there’s going to be no faster way to get to C right because that is the shortest edge out of A. Any of the longer edges we’re assuming we can’t take negative weight edges that would cause this four to get smaller than the three. All we really know is that this three is the smallest. What we should do is not expand B, but we should focus on C. We now know that there’s a path that actually can get us there in 13. This 10 edge plus the three that it takes to get to C. We can get to B faster than 15. We can get to B in 13. Now, is that the shortest possible path for B? We don’t know cause we know that we could get to D in four and maybe there’s a link one, I mean ignoring the graph for a second. Maybe, there’s a link one path that would get us to B, which would be even shorter. All we know from what we’ve done so far is that the shortest path from A to D is four. Let’s lock that down and pull D off of the open list, and let’s focus on D. D has edges to B, F, and E. Here’s B, and here’s F and E. This path to F through D is going to add another seven for a total of 11, and this path to E through D is going to add another three for a length of seven, and remember there’s also a D to B link, which would add nine to this, which would get us there in 13, and we already knew how to get there in 13, so that doesn’t really change anything. Based on these three, we know the fastest way to A, C, and D, and once that we have also been able to reach, we know that E has the shortest distance, which is seven, and there isn’t going to be any faster way to get to E cause there aren’t any other nodes that we could get to and then get to E faster than seven. We can lock that one down, pull off the open list, add all its edges to the non-completed nodes. E can go to F, and it has a link of five. We could go seven steps to E and then another five to F for a total of 12. No, we can already get there in 11. That’s probably not a good idea.>From E, we can also get to G in one step, which would have been seven plus the additional step for a total of eight, and that’s all we can reach from E. Looking things over, we now know that the fastest way to get to G is eight steps because the only other way we could get to G would be to visit one of the other nodes, and then go to G, and that would have to be longer than eight. We’re going to lock it down, and now we pull of the open list and look at the edges out of G. G can get to F in two steps, and that’s an improvement because before the best we could get to F was 11 steps. Now, we can get to F in ten. Can we get anywhere else new? No, cause the only nodes that are complete now are B and F, and they’re already in the picture, and in fact, now we see that the fastest way to get to F is going to be in ten steps cause the only other way to get to F that we haven’t considered is getting there through B, and that’s going to be longer. We can lock this down. Alright! So, let’s look at F. What edges are coming at F to uncompleted nodes, just this one to B. That would have been F is ten steps plus one more would be 11 to get to B. That’s an improvement over what we had before, and that’s it for F. Now, the only node that we’ve got left to think about is B. There’s no way to get to be any faster than 11 cause there’s no other place that we can go and then get to B. We can lock it down, and that finishes the picture. We now know what the shortest distance is from A to===in the graph. The distance to B is 11. Now, we’ve kind of lost a little bit of information of how we get to B in 11? But, we’ll deal with that in a little bit.

Leave a Reply

Your email address will not be published. Required fields are marked *