Hey guys welcome to a tutorial on the shortest path algorithm for networks and
you would need to know a little bit about networks what are nodes what are
arcs and preferably you would have seen the minimal spanning tree tutorial
before you do the shortest path tutorial and now what is the difference between
shortest path and minimal spanning tree and basically the difference is that in
a minimum spanning tree you need to make sure that all the nodes are connected to
your tree whereas with the shortest path you just find the shortest way to go
from one node to the other node and you don't have to pass through all the nodes
so let's have a look at this network here as a simple example so let's say
you're standing at A ok you're standing at this spot here and you can see that
and let's say we want to get to C so we want to find a shortest path from A to C
from A to C now we want to get to C this is our destination and what is the
shortest way to get there well we know that it's going to take us
initially zero distance we're going to it's going to take us ten steps to get
to B it's going to take us eleven steps to get to D ok so we're going to label
that first and then what happens is from D to C 11 plus 2 is 13 whereas 10 plus 4
is 14 so if we go from D we can get to C at 13 and that is our shortest path
so our shortest path from A to C would be ADC and the total arc length is 11
plus 2 which is 13 okay so it's pretty easy when you have a simple network like
that one now if I give you a more complicated network okay so I have just
made up a network find the shortest path from A to B a is here B is there and
here is a shortest path algorithm step one for all nodes one step away
from the beginning
find the distance to arrive at the node
to arrive at the node so step one is simply we decided that we want to begin
at A as stated in the question and one step away from A we have five two and
three so initially we have zero takes us three steps to get to this node two
steps to get to that node five steps to get to that node
now step two and we're going to repeat step one
for all nodes two steps away
from the beginning and I should say that we need to find the shortest distance
shortest distance and what that means is for example this circle right here this
node right here is two steps away from A and we have two ways of getting there we
can either go 3 plus 4 which is 7 or 2 plus 8 is 10 now the shortest distance
would be 7 okay now let's look at this one here which is also two steps away 3
plus 10 is 13 7 plus 4 is 11 so we're going to put 11 there this one is two
steps away so 2 plus 9 is 11 5 plus 3 is 8 so we're going to put 8 step 3 repeat
step 2 until destination is reached
until destination is reached so then we just have to go 7 plus 2 is 9 11 plus 11
22 that's way too big 8 plus 7 is 15 so 9 is a shortest ok step 4 trace back to
the beginning trace back to the beginning to find the shortest path
so from the end which is here we're going to find out how we got nine how
did we get night well nine came from seven so we're going to connect that
seven came from four so we're going to connect that and three came from A we're
going to connect that so that is our shortest path okay thanks for watching
the tutorial I hope you got a better understanding of shortest path see you
next time.