Tip:
Highlight text to annotate it
X
So suppose we want to travel from Tacoma over here to Yakima over here and there's
a few routes we can take. Either down through Eatonville and
Packwood or through Auburn and Northbend or through Auburn and Mt.
Rainer and its not quite clear which route is fastest.
And so we're going to use something called Dijkstra's algorithm, which solves
this, what's called the shortest path problem.
So we're going to start by saying we're going to start by looking at our ending
vertex and saying, I know that this vertex is 0 miles from the end.
Why? because it is the end.
And so next we're going to look at the, all the vertices that lead to Yakima.
So for each of these we're going to figure out how far it is from the end.
So this one is 104 miles from the end. This one is 96 miles from the end.
This one is 76 miles from the end and now, that's sort of our first step.
So next thing we're going to do is we're going to identify our next current vertex
so we go to the vertex that is. The closest to the end.
So we're going to identify the the vertex as the smallest distance, that's this
one. We're going to identify it as current and
so now from that vertex we're going to work backwards and say, what vertices
lead to this one? So going this way, we say, 76 plus 96 is
172. And then we say, 76 plus 27, let's here,
76 plus 27 is 103. But 103 is longer than 96 and so we're
not going to record that one, because that one doesn't help us any.
Remember we're trying to get shortest distances.
And so it's shorter to go directly from Mount Rainier to Yakima than to go from
Mount Rainier to Packwood to Yakima, right?
That was what that 103 told us is that the combined length here is 103 and
that's longer so we don't want it. Okay.
So now that we're done with that vertex, we mark our next vertex, our next
shortest vertex, as Current. And we work backwards from there so we
say the only leading thing leading to there is, is this edge here so, we work
backwards 96 here plus another 79 here gives me a time of let's see 175.
for, for that one. Okay.
And that was the only edge leading in so now we're done with that one, and we'll
move on to our next shortest edge here and work backwards.
So notice now that working backwards from here.
This distance is 104 this time, I guess these aren't times, anyway, the, this
time is, is 36, and 36 plus 104, right, 104 minutes here, 36 minutes there, is a
total of 140. And 140 is shorter than 175.
So, we're going to replace that 175 with 140 because that was a shorter that was a
shorter path and we were looking for the shortest path here.
So now, all three of these vertices we've already looked at.
So now we move to the next vertex that is shortest, and that is this one.
From here again, we work backwards. So 140 plus 20 is 160, and, now we're
done with that vertex, we come down here. 172 plus 57 is, I don't know what it is
but it certainly bigger than 160 and so we don't care.
And so we have found our shortest path. Our shortest path has a total travel time
of 160 and it look like it routes through Auburn, through North Bend Down to
Yakima. And so that is the shortest path found
through Dijkstra's algorithm.