OK so we're going to do the extra shortest path here.
The havinga graph set up over here and there are weights on these who are going to find the minimum
weight to get from A to Z.
So we are going to start at a different.
There's different approaches of course to shortest path.
One of those approaches includes things like counting every path to any path.
In other words from A to anything the shortest path you know eccentric.
We're going to do dikes just from one point to another.
They should just pass them to eat.
So I started with a over gear and I ended with E over here just because that's the last one that I want
to get to.
OK.
So let's take an accounting of how much everything costs.
So A to B is A is 0 8 and B is 2 and that's through a A to G is 3.
So to use three and again that's true.
And Ada f is 6.
And that's again through a.
Now anything that I didn't put down I can't get to.
So I can put an infinity symbol like this I can put an X it just has to be it's bigger than anything
that we know and it's in this case irrelevant to do anything more a is my small list over here.
So I'm just going to say are going to highlight it like that and I'm going to leave it in there.
So we're good now.
The next smallest is to be.
So I'm going to go to B cause that right now is my shortest path towards anything.
So I'm going to write down the two through a cause that's how I got there.
B connects to C and it's 5 to C but to get to be in the first place was to and then to get to see from
this because it is from A to get to see from this it's fives all together you get seven.
And that would be from B because now it's from B to get to the 7 the G.
We can get to that G from B and write that G.
Well we could go three.
And then to get to to get to G.
Would be for.
But that would be two plus four would be six.
But right now it's three.
So we may as well keep it at this at a because that's the easiest way to get there.
OK.
Let's see h would be two plus two is four.
Now we don't have anything yet for either.
So we'll go with that.
And then everything else is the same because we have no quicker way to get to anything else directly
from there.
So for instance D we can get two so we can put symbol f..
It would be silly to do this this this instead of just going.
Well f is 6 or maybe perhaps now because we tend to do that so I'd be silly.
So f is is that.
We can get to an E.
We can get two.
OK.
Now the two here is the smallest.
So I'm just going to highlight that because that would be the quickest way to get to me would be from
two from and so will highlight that and then we'll go to the next month which is G because in our paths
G is the next smallest thing to get to.
Now if we go to G we have the three from a.
That's the easiest way to get there.
So we'll put that out over here.
And what we're going to do is we're going to see what else we can get to.
So be I already know that I have a shorter way of getting there from B.
So it's not going to help to go through G to get to B C H H right now has a way of getting 2 to 4.
If I went through G that would be three plus five is eight.
So it's not going to help.
So we may as well just keep it at 4.
OK.
We also have we also have see we're being being being not nothing.
There's nothing else actually that that would be smart to go through.
You can go through life.
But again that would be silly to do that.
So essentially what we're going to do because it connects to F but f is already 6.
And that would be more to get there.
So it really helps.
So.
Well actually no I'm sorry.
We could do.
We can go g and then f.
So that would be three plus one is four.
So this would be four and that four would be that four would be the easy way to get to F and that would
be that 4 would be through GTS on the right there.
So that would actually make sense to go through G that way.
So if I wanted to get to F for some reason that would probably be a a better path.
So the C stays the same because that doesn't help at all to go through that way.
That's still best from B the D.
Still nothing because we don't have any way of getting there.
Again we have no way of getting there in the E.
We have no way of getting there.
So when I'm going to do is I have the Threes the smallest.
So I to do was I going to pick the three are going to be right here I'm going to pick three and then
I'm going to know that I'm going to go through G.
OK so three three is not so good.
And then the smallest that I have over here is either the f or the H.
Now I'm just going to go to f.
But it doesn't make a difference which you pick are going to go to F and I'm going to bring down this.
So the smallest way to get to half is to go through the metal before.
So if I went through G then I trace where g went through and G went through a the smallest so then that
would be the smallest way to get there.
OK.
So let's see what this connects to.
This connects to the high is ones that would be four plus one is five.
So I can get two through half and that's five.
There's nothing else that connects to here.
So therefore what we're going to do is we're just going to drag everything else down and write this
in.
There's nothing else that connects to the still that a we've finished with because we highlighted the
H.
We don't have any quicker connections than that.
So the quickest connection is still for B.
And then the we're not doing anything with.
Now we can pick.
We have to pick what is the smallest over here to do and I finished with this.
So that was what I just did that.
Gees I'm going to highlight this kid because that's when I just did.
And now the smallest is the h.
So I'm going to say I'm going to put my h over here and I'm going to drag this down so that h the quickest
way to get to H would be from there.
Because we trace it from the B and then to be traced from a.
Because that's the way.
So we have that now.
H can X to Y Y.
Would be how long it takes to get it takes to get the h in the smallest so far which is four plus eight
would be 12.
So to get to ID we really have a shorter path which is five through F..
So we're going to just write that down because that's the shorter path from there.
OK.
H.
Which is what we're on.
Also connects to see.
So let's just look at c over here H connects to C so H has for it to get to see would be another force
that would be a.
So far we really can get to see by 7.
So therefore I'm not going to change that either because I really have a shorter path to get them to
get to me.
I can do aitches four in the IS THAT would be five.
So I'm going to write that down.
To me.
It may be the shortest path may not.
For now I'm just going to highlight that as is.
And that's going to count everything.
So d i can get two still and everything else is done.
Now I used this h over here so I'm going to highlight this it now I'm going to pick the next lowest
number.
Now I can pick either of these I'm just going to go with I I'm going to record everything that I've
done.
So the easiest way to get to it is from there let's see what else on the either.
H but H was already finished either.
So that would be he got to be five plus six as 11.
Well I have an easier way of getting to easy.
So I'm not going to record that in there.
And then the D.
I still can't get to and see.
I still have no better way of doing with.
So therefore that's that.
OK.
So I used this over here and now I have an easy like this.
And so that is that is that 5 is going to be from the east or I'll put the E over here and I'll drag
this down.
OK.
And let's see.
I have e.
Well e connects to the.
And that would be that would be what is to is five six seven eight.
So the could be eight.
And that's from the E doesn't connect to the C at all so well it would but it would be more than it
is because it would take 12.
So that's still going to be 7 is going to be B and everything else is done.
So I'm just going to highlight my this which is what I brought down and I'm going to continue on.
Now you might say just stop there because I got to eat.
True but I'd like to finish the whole thing.
So I'm going to go to the next one which is c c connects to H but H was already done because that's
done C connects to D.
So C anyway is going to be dragged down and that's going to be the smallest trouble I'm going to highlight
that because we know that that's going to be and that's going to be what we're going to how we're going
to get there into D would be 8 plus 12 8 plus 12 is wizardry 7 plus 12 7 plus 12 to get to D is going
to be greater than if I just went through.
So I'm going to say that that's going to stick like that.
And then I'm just going to drag it down.
So I have my last one here and I ain't going through like that.
So even to get to the you know we could actually trace we could actually trace that in that fashion.
But overall I do see that I can get to what I would like to get to which is my easy to do.
This was I like that over here to give me an easy way to get to it as we trace it backwards.
The way that I could overhear here didn't come from any age.
It came from age.
OK.
I'm sorry that was us moms they came from age so let's just erase those came from H.
Not to not he.
So it came from H.
The five came from age.
So this he came from H.
OK.
So that he came from age well that age if we go if we write that came from age that age came from the
smallest one was came from B.
B came from a.
And so altogether.
So I got five which in the path that I took to get there was this this this.
So for a small graph you might be able to figure out what that path is but for a large graph we want
to just keep track of everything.
So one important thing to keep track of always is where it's coming from my road be over here by accident.
Surely just a pedagogical for pedagogical purposes.
But the point is that H that this e comes from H.
And that's why I want to say 5 h because that's where it comes from.
Then I drag them down and then I drag that down again for that five.
So you want to always put where it's coming from and if you know where it's coming from then you can
always just trace it back.
So that's our Dykstra shortest path.
What we do is we follow it along and we do each option we trace where it's coming from for this thing.
So there you go.
DYKSTRA as short as Ben.